#include <stdio.h>
#include <stdlib.h>
#include <math.h>

char *Progname;
char Usage[] = "usage: %s [file]\n";
#define USAGE() fprintf(stderr, Usage, Progname)

#define MAX 100000

float *Data;

int Sflag;

void doit(FILE *);
float rescaled_range(float *, int);
void shuffle(float *, int);
void sfrand();
int rnd(int);

int main(int argc, char **argv)
{
	register char *curr_arg;
	register int c;
	FILE *infile;

	Progname = *argv;

	/* Parse arguments beginning with a hyphen. */

	Sflag = 0;
	while (--argc > 0 && **++argv == '-' && *(curr_arg = 1 + *argv)) {

		/* Scan current argument until a flag indicates that the rest
		of the argument isn't flags (curr_arg = NULL), or until
		the end of the argument is reached (if it is all flags). */

		while (curr_arg != NULL && (c = *curr_arg++) != '\0') {
			switch (c) {

			case 's':
				Sflag = 1;
				break;

			default:
				fprintf(stderr, "%s: unknown flag -%c\n", Progname, c);
				USAGE();
				exit(1);
			}
		}
	}

	/* Process the named file, or stdin if no file given.
	The name '-' also specifies stdin. */

	infile = stdin;
	if (argc && **argv != '-') {
		if ((infile = fopen(*argv, "r")) == NULL) {
			fprintf(stderr, "%s: can't open '%s'\n", Progname, *argv);
			exit(1);
		}
	}

	doit(infile);

	return 0;
}

void
doit(FILE *infile)
{
	int i, j, n, p;
	float f, sum;
	float *fp;
	char buf[100];

	/* Read the data. */

	Data = (float *)malloc(MAX * sizeof(float));

	fp = Data;
	n = 0;
	while (fgets(buf, 100, infile)) {
		*fp++ = atof(buf);
		n++;
	}

	if (Sflag) {
		sfrand();
		shuffle(Data, n);
	}

	/* Get the rescaled range for a series of segments of the data. */

	for (p = n, j = 1; p > 2; p >>= 1, j <<= 1) {
		fp = Data;
		sum = 0.0;
		for (i = 0; i < j; i++) {
			f = rescaled_range(fp + i * p, p);
			sum += f;
		}
		printf("%d %g\n", p, sum / j);
	}

	free(Data);
}

float
rescaled_range(float *data, int n)
{
	int i;
	float f, x;
	float mean, sdev;
	float min, max, range;
	float sum, sumsq;
	float *fp;

	/* Get the mean. */

	fp = data;
	sum = 0.0;
	for (i = 0; i < n; i++) {
		sum += *fp++;
	}
	mean = sum / n;

	/* Get the variance and the range of the
	accumulated deviation from the mean. */

	fp = data;
	sumsq = x = 0.0;
	min = 1.0e30;
	max = -1.0e30;
	for (i = 0; i < n; i++) {
		f = *fp++ - mean;
		x += f;
		if (x > max) max = x;
		if (x < min) min = x;
		sumsq += f * f;
	}
	sdev = sqrt(sumsq / n);
	range = max - min;

	if (sdev != 0.0) {
		return (range / sdev);
	}
	return (0.0);
}

/* Create a random permutation by making n - 1 random exchanges. */

void
shuffle(float *array, int n)
{
	int i, j;
	float t;

	for (i = n - 1; i > 0; --i) {

		/* Select a random array element, from 0 to i. */

		j = rnd(i + 1);

		/* Exchange. */

		t = array[i];
		array[i] = array[j];
		array[j] = t;
	}
}

/* Random numbers from Numerical Recipes, 2nd edition. */

#define IM1 2147483563
#define IA1 40014
#define IQ1 53668
#define IR1 12211

#define IM2 2147483399
#define IA2 40692
#define IQ2 52774
#define IR2 3791

#define AM (1.0 / IM1)
#define IMM1 (IM1 - 1)
#define NTAB 32
#define NDIV (1 + (IMM1 / NTAB))
#define EPS 6.0e-8
#define RNMX (1.0 - EPS)

long Frand_seed = -1;

static long iv[NTAB];
static long l, l2, iy;

void
sfrand()
{
	int j;
	long k, time();

	l = Frand_seed;
	if (l < 0) {
		l = time(0);
	}
	l++;
	l2 = l;

	for (j = NTAB + 7; j >= 0; --j) {
		k = l / IQ1;
		l = IA1 * (l - k * IQ1) - k * IR1;
		if (l < 0) {
			l += IM1;
		}
		if (j < NTAB) {
			iv[j] = l;
		}
	}
	iy = iv[0];
}

/* Returns a uniform random number in the interval (0.0, 1.0). */

float
frand()
{
	int j;
	long k;

	k = l / IQ1;
	l = IA1 * (l - k * IQ1) - k * IR1;
	if (l < 0) {
		l += IM1;
	}

	k = l2 / IQ2;
	l2 = IA2 * (l2 - k * IQ2) - k * IR2;
	if (l2 < 0) {
		l2 += IM2;
	}

	j = iy / NDIV;
	iy = iv[j] - l2;
	iv[j] = l;
	if (iy < 1) {
		iy += IMM1;
	}

	return ((float)AM * iy);
}

/* Return a random number between 0 and range - 1, inclusive. */

int
rnd(int range)
{
	return ((int)(frand() * range));
}