#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
double sr = 0, pr = 0;
int pyramid_sort(int *a, int *b)
{
	int t = *a;
	*a = *b;
	*b = t;
	return 0;
}
int main()
{
	int i, n, j, step, b;
	scanf("%d", &n);
	int *arr = calloc(n, sizeof(int));
	double elapsed;
	double time;
	/*srand(time(NULL));*/
	clock_t start, end;
	/*time_t start, end;
	start = time(NULL);*/
	for (j= 0; j < 1000; j++)
	{
		step = 0;
		b = 0;
		for (i = 0; i < n; i++)
		{
			arr[i] = rand();
		}
		start = clock();
		while (1)
		{
			b = 0;
			for (i = 0; i < n; ++i)
			{
				if (i * 2 + 2 + step < n)
				{
					if (arr[i + step] > arr[i * 2 + 1 + step] || arr[i + step] > arr[i * 2 + 2 + step])
					{
						sr++;
						if (arr[i * 2 + 1 + step] < arr[i * 2 + 2 + step])
						{
							pyramid_sort(&arr[i + step], &arr[i * 2 + 1 + step]);
							pr++;
							b = 1;
						}
						else
						{
							sr++;
							if (arr[i * 2 + 2 + step] < arr[i * 2 + 1 + step])
							{
								pyramid_sort(&arr[i + step], &arr[i * 2 + 2 + step]);
								pr++;
								b = 1;
							}
						}
					}
				}
				else if (i * 2 + 1 + step < n)
				{
					sr++;
					if (arr[i + step] > arr[i * 2 + 1 + step])
					{
						pyramid_sort(&arr[i + step], &arr[i * 2 + 1 + step]);
						b = 1;
						pr++;
					}
				}
			}
			if (!b)
				step++;
			if (step + 2 == n)
				break;
		}
		end = clock();
		elapsed = (double)(end - start) / CLOCKS_PER_SEC;
		time += elapsed;
	}
	/*end = time(NULL);*/
	printf("\n");
	//printf("time %f sec.\n", difftime(end, start));
	printf("time %.7f \n", time);
	printf("\n");
	printf("%lf ", ((sr+pr) / 1000));
	printf("\n");
	//printf("%lf ", (pr / 1000));
	return 1;
}