#include <iostream>
#include <ctime>
#include <cmath>
#include <limits>
using namespace std;

#include "Skip_list.h"
using namespace Data_structures;

int const M = 100000;

int main() {
	for ( int N = 4; N < 10000; N += 13 ) {
		double s = 0.0;
		double ss = 0.0;
		double minimum = numeric_limits<double>::infinity();
		double maximum = 0.0;

		for ( int k = 0; k < M; ++k ) {
			srand( k );
			Skip_list<int, int> skip;

			for ( int i = 0; i < N; ++i ) {
				skip[i];
			}

			double ave = skip.average_search();

			s += ave;
			ss += ave*ave;
			minimum = std::min( ave, minimum );
			maximum = std::max( ave, maximum );
		}

		double sd = std::sqrt( ss/M - (s/M)*(s/M) );
		cout << N << "\t" << s/M  << "\t" << sd << "\t" << minimum << "\t" << maximum << endl;
	}

	return 0;
}