#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
using namespace std;
 
using ld = double;
using vld = vector<ld>;
 
vld generate(int n)
{
	vld result;
	for (; n > 0; n--)
		result.push_back(ld(1) / n / n);
	reverse(result.begin(), result.end());
	return result;
}
 
ld sum_series()
{
	ld pi = acos(ld(0)) * 2;
	return pi * pi / 6;
}
 
ld sum_naive(vld v)
{
	ld result = 0;
	for (auto d : v)
		result += d;
	return result;
}
 
ld sum_recursive_range(const vld &v, int l, int r)
{
	if (l == r)
		return v[r];
 
	int mid = (l + r) / 2;
	return sum_recursive_range(v, l, mid) + sum_recursive_range(v, mid + 1, r);
}
 
ld sum_recursive(vld v)
{
	random_shuffle(v.begin(), v.end());
	return sum_recursive_range(v, 0, (int)v.size() - 1);
}
 
ld sum_huffman(vld v)
{
	priority_queue<ld, vector<ld>, greater<ld>> q(v.begin(), v.end());
	while (q.size() != 1)
	{
		auto d1 = q.top();
		q.pop();
		auto d2 = q.top();
		q.pop();
		q.push(d1 + d2);
	}
	return q.top();
}
 
void dump(string prefix, ld x)
{
	cout << prefix << ": " << x << " (error " << fabs(x - sum_series()) << ")" << endl;
}
 
void dump(int n)
{
	auto v = generate(n);
 
	cout << "Case #" << n << endl;
	dump("Naive direct", sum_naive(v));
	reverse(v.begin(), v.end());
	dump("Naive reversed", sum_naive(v));
 
	dump("Recursive 1", sum_recursive(v));
	dump("Recursive 2", sum_recursive(v));
	dump("Recursive 3", sum_recursive(v));
	dump("Recursive 4", sum_recursive(v));
 
	dump("Huffman", sum_huffman(v));
}
 
int main()
{
	srand(322);
 
	cout.setf(ios::fixed);
	cout.precision(20);
 
	cout << "Series sum: " << sum_series() << endl;
	dump(10000000);
 
	return 0;
}
 
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8ZnVuY3Rpb25hbD4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxzdHJpbmc+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp1c2luZyBsZCA9IGRvdWJsZTsKdXNpbmcgdmxkID0gdmVjdG9yPGxkPjsKCnZsZCBnZW5lcmF0ZShpbnQgbikKewoJdmxkIHJlc3VsdDsKCWZvciAoOyBuID4gMDsgbi0tKQoJCXJlc3VsdC5wdXNoX2JhY2sobGQoMSkgLyBuIC8gbik7CglyZXZlcnNlKHJlc3VsdC5iZWdpbigpLCByZXN1bHQuZW5kKCkpOwoJcmV0dXJuIHJlc3VsdDsKfQoKbGQgc3VtX3NlcmllcygpCnsKCWxkIHBpID0gYWNvcyhsZCgwKSkgKiAyOwoJcmV0dXJuIHBpICogcGkgLyA2Owp9CgpsZCBzdW1fbmFpdmUodmxkIHYpCnsKCWxkIHJlc3VsdCA9IDA7Cglmb3IgKGF1dG8gZCA6IHYpCgkJcmVzdWx0ICs9IGQ7CglyZXR1cm4gcmVzdWx0Owp9CgpsZCBzdW1fcmVjdXJzaXZlX3JhbmdlKGNvbnN0IHZsZCAmdiwgaW50IGwsIGludCByKQp7CglpZiAobCA9PSByKQoJCXJldHVybiB2W3JdOwoKCWludCBtaWQgPSAobCArIHIpIC8gMjsKCXJldHVybiBzdW1fcmVjdXJzaXZlX3JhbmdlKHYsIGwsIG1pZCkgKyBzdW1fcmVjdXJzaXZlX3JhbmdlKHYsIG1pZCArIDEsIHIpOwp9CgpsZCBzdW1fcmVjdXJzaXZlKHZsZCB2KQp7CglyYW5kb21fc2h1ZmZsZSh2LmJlZ2luKCksIHYuZW5kKCkpOwoJcmV0dXJuIHN1bV9yZWN1cnNpdmVfcmFuZ2UodiwgMCwgKGludCl2LnNpemUoKSAtIDEpOwp9CgpsZCBzdW1faHVmZm1hbih2bGQgdikKewoJcHJpb3JpdHlfcXVldWU8bGQsIHZlY3RvcjxsZD4sIGdyZWF0ZXI8bGQ+PiBxKHYuYmVnaW4oKSwgdi5lbmQoKSk7Cgl3aGlsZSAocS5zaXplKCkgIT0gMSkKCXsKCQlhdXRvIGQxID0gcS50b3AoKTsKCQlxLnBvcCgpOwoJCWF1dG8gZDIgPSBxLnRvcCgpOwoJCXEucG9wKCk7CgkJcS5wdXNoKGQxICsgZDIpOwoJfQoJcmV0dXJuIHEudG9wKCk7Cn0KCnZvaWQgZHVtcChzdHJpbmcgcHJlZml4LCBsZCB4KQp7Cgljb3V0IDw8IHByZWZpeCA8PCAiOiAiIDw8IHggPDwgIiAoZXJyb3IgIiA8PCBmYWJzKHggLSBzdW1fc2VyaWVzKCkpIDw8ICIpIiA8PCBlbmRsOwp9Cgp2b2lkIGR1bXAoaW50IG4pCnsKCWF1dG8gdiA9IGdlbmVyYXRlKG4pOwoKCWNvdXQgPDwgIkNhc2UgIyIgPDwgbiA8PCBlbmRsOwoJZHVtcCgiTmFpdmUgZGlyZWN0Iiwgc3VtX25haXZlKHYpKTsKCXJldmVyc2Uodi5iZWdpbigpLCB2LmVuZCgpKTsKCWR1bXAoIk5haXZlIHJldmVyc2VkIiwgc3VtX25haXZlKHYpKTsKCglkdW1wKCJSZWN1cnNpdmUgMSIsIHN1bV9yZWN1cnNpdmUodikpOwoJZHVtcCgiUmVjdXJzaXZlIDIiLCBzdW1fcmVjdXJzaXZlKHYpKTsKCWR1bXAoIlJlY3Vyc2l2ZSAzIiwgc3VtX3JlY3Vyc2l2ZSh2KSk7CglkdW1wKCJSZWN1cnNpdmUgNCIsIHN1bV9yZWN1cnNpdmUodikpOwoKCWR1bXAoIkh1ZmZtYW4iLCBzdW1faHVmZm1hbih2KSk7Cn0KCmludCBtYWluKCkKewoJc3JhbmQoMzIyKTsKCgljb3V0LnNldGYoaW9zOjpmaXhlZCk7Cgljb3V0LnByZWNpc2lvbigyMCk7CgoJY291dCA8PCAiU2VyaWVzIHN1bTogIiA8PCBzdW1fc2VyaWVzKCkgPDwgZW5kbDsKCWR1bXAoMTAwMDAwMDApOwoKCXJldHVybiAwOwp9Cgo=