#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <chrono>
using namespace std;
using namespace std::chrono;

vector<int> readArray() {
	int aSize;
	scanf("%d", &aSize);
	vector<int> a(aSize);
	for (int i = 0; i < aSize; i++)
		scanf("%d", &a[i]);
	return a;
}

int random(int l, int r) {
	return l + rand() % (r - l + 1);
}

vector<int> generateArray(int size) {
	vector<int> a(size);
	for (int i = 0; i < size; i++)
		a[i] = random(-100, 100);
	return a;
}

int lisLength(vector<int> &a) {
	vector<int> length(a.size());
	int maxLength = 0;
	for (int i = 0; i < a.size(); i++) {
		length[i] = 1;
		for (int j = 0; j < i; j++) {
			if (a[j] < a[i] && length[i] < length[j] + 1)
				length[i] = length[j] + 1;
		}
		if (maxLength < length[i])
			maxLength = length[i];
	}
	return maxLength;
}

double singleTimeTest(int size) {
	vector<int> a = generateArray(size);
	high_resolution_clock::time_point startTime = high_resolution_clock::now();
	lisLength(a);
	high_resolution_clock::time_point finishTime = high_resolution_clock::now();
	duration<double> elapsedTime = duration_cast<duration<double>>(finishTime - startTime);
	return elapsedTime.count();
}

double multipleTimeTests(int size, int testsCount) {
	double totalTime = 0;
	for (int i = 0; i < testsCount; i++)
		totalTime += singleTimeTest(size);
	return totalTime / testsCount;
}

void timeTestingTable() {
	printf("N\tT(N)\n");
	for (int n = 16; n <= 4096; n *= 2)
		printf("%d\t%lf\n", n, multipleTimeTests(n, 100));
}

int main() {
	timeTestingTable();
}