#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
using namespace std;
 
using ld = double;
using vld = vector<ld>;
using vi = vector<int>;
 
ld base()
{
	return atan(ld(2.718281828));
}
 
pair<vld, ld> generate(int n)
{
	vi test;
	for (; n > 0; n--)
		test.push_back(rand() % 10);
 
	vld result;
	int sum = 0;
	for (auto d : test)
	{
		result.push_back(base() * d);
		sum += d;
	}
 
	return { result, sum * base() };
}
 
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, ld sum)
{
	cout << prefix << ": " << x << " (error " << fabs(x - sum) << ")" << endl;
}
 
void dump(int n)
{
	auto input = generate(n);
	auto v = input.first;
 
	sort(v.begin(), v.end());
 
	cout << "Case n = " << n << endl;
	cout << "Series sum: " << input.second << endl;
 
	dump("Naive direct", sum_naive(v), input.second);
	reverse(v.begin(), v.end());
	dump("Naive reversed", sum_naive(v), input.second);
 
	dump("Recursive 1", sum_recursive(v), input.second);
	dump("Recursive 2", sum_recursive(v), input.second);
	dump("Recursive 3", sum_recursive(v), input.second);
	dump("Recursive 4", sum_recursive(v), input.second);
 
	dump("Huffman", sum_huffman(v), input.second);
}
 
int main()
{
	srand(322);
 
	cout.setf(ios::fixed);
	cout.precision(20);
 
	dump(100000);
	dump(100000);
	dump(1000000);
	dump(1000000);
 
	return 0;
}
 
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8ZnVuY3Rpb25hbD4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxzdHJpbmc+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp1c2luZyBsZCA9IGRvdWJsZTsKdXNpbmcgdmxkID0gdmVjdG9yPGxkPjsKdXNpbmcgdmkgPSB2ZWN0b3I8aW50PjsKCmxkIGJhc2UoKQp7CglyZXR1cm4gYXRhbihsZCgyLjcxODI4MTgyOCkpOwp9CgpwYWlyPHZsZCwgbGQ+IGdlbmVyYXRlKGludCBuKQp7Cgl2aSB0ZXN0OwoJZm9yICg7IG4gPiAwOyBuLS0pCgkJdGVzdC5wdXNoX2JhY2socmFuZCgpICUgMTApOwoKCXZsZCByZXN1bHQ7CglpbnQgc3VtID0gMDsKCWZvciAoYXV0byBkIDogdGVzdCkKCXsKCQlyZXN1bHQucHVzaF9iYWNrKGJhc2UoKSAqIGQpOwoJCXN1bSArPSBkOwoJfQoKCXJldHVybiB7IHJlc3VsdCwgc3VtICogYmFzZSgpIH07Cn0KCmxkIHN1bV9uYWl2ZSh2bGQgdikKewoJbGQgcmVzdWx0ID0gMDsKCWZvciAoYXV0byBkIDogdikKCQlyZXN1bHQgKz0gZDsKCXJldHVybiByZXN1bHQ7Cn0KCmxkIHN1bV9yZWN1cnNpdmVfcmFuZ2UoY29uc3QgdmxkICZ2LCBpbnQgbCwgaW50IHIpCnsKCWlmIChsID09IHIpCgkJcmV0dXJuIHZbcl07CgoJaW50IG1pZCA9IChsICsgcikgLyAyOwoJcmV0dXJuIHN1bV9yZWN1cnNpdmVfcmFuZ2UodiwgbCwgbWlkKSArIHN1bV9yZWN1cnNpdmVfcmFuZ2UodiwgbWlkICsgMSwgcik7Cn0KCmxkIHN1bV9yZWN1cnNpdmUodmxkIHYpCnsKCXJhbmRvbV9zaHVmZmxlKHYuYmVnaW4oKSwgdi5lbmQoKSk7CglyZXR1cm4gc3VtX3JlY3Vyc2l2ZV9yYW5nZSh2LCAwLCAoaW50KXYuc2l6ZSgpIC0gMSk7Cn0KCmxkIHN1bV9odWZmbWFuKHZsZCB2KQp7Cglwcmlvcml0eV9xdWV1ZTxsZCwgdmVjdG9yPGxkPiwgZ3JlYXRlcjxsZD4+IHEodi5iZWdpbigpLCB2LmVuZCgpKTsKCXdoaWxlIChxLnNpemUoKSAhPSAxKQoJewoJCWF1dG8gZDEgPSBxLnRvcCgpOwoJCXEucG9wKCk7CgkJYXV0byBkMiA9IHEudG9wKCk7CgkJcS5wb3AoKTsKCQlxLnB1c2goZDEgKyBkMik7Cgl9CglyZXR1cm4gcS50b3AoKTsKfQoKdm9pZCBkdW1wKHN0cmluZyBwcmVmaXgsIGxkIHgsIGxkIHN1bSkKewoJY291dCA8PCBwcmVmaXggPDwgIjogIiA8PCB4IDw8ICIgKGVycm9yICIgPDwgZmFicyh4IC0gc3VtKSA8PCAiKSIgPDwgZW5kbDsKfQoKdm9pZCBkdW1wKGludCBuKQp7CglhdXRvIGlucHV0ID0gZ2VuZXJhdGUobik7CglhdXRvIHYgPSBpbnB1dC5maXJzdDsKCglzb3J0KHYuYmVnaW4oKSwgdi5lbmQoKSk7CgoJY291dCA8PCAiQ2FzZSBuID0gIiA8PCBuIDw8IGVuZGw7Cgljb3V0IDw8ICJTZXJpZXMgc3VtOiAiIDw8IGlucHV0LnNlY29uZCA8PCBlbmRsOwoKCWR1bXAoIk5haXZlIGRpcmVjdCIsIHN1bV9uYWl2ZSh2KSwgaW5wdXQuc2Vjb25kKTsKCXJldmVyc2Uodi5iZWdpbigpLCB2LmVuZCgpKTsKCWR1bXAoIk5haXZlIHJldmVyc2VkIiwgc3VtX25haXZlKHYpLCBpbnB1dC5zZWNvbmQpOwoKCWR1bXAoIlJlY3Vyc2l2ZSAxIiwgc3VtX3JlY3Vyc2l2ZSh2KSwgaW5wdXQuc2Vjb25kKTsKCWR1bXAoIlJlY3Vyc2l2ZSAyIiwgc3VtX3JlY3Vyc2l2ZSh2KSwgaW5wdXQuc2Vjb25kKTsKCWR1bXAoIlJlY3Vyc2l2ZSAzIiwgc3VtX3JlY3Vyc2l2ZSh2KSwgaW5wdXQuc2Vjb25kKTsKCWR1bXAoIlJlY3Vyc2l2ZSA0Iiwgc3VtX3JlY3Vyc2l2ZSh2KSwgaW5wdXQuc2Vjb25kKTsKCglkdW1wKCJIdWZmbWFuIiwgc3VtX2h1ZmZtYW4odiksIGlucHV0LnNlY29uZCk7Cn0KCmludCBtYWluKCkKewoJc3JhbmQoMzIyKTsKCgljb3V0LnNldGYoaW9zOjpmaXhlZCk7Cgljb3V0LnByZWNpc2lvbigyMCk7CgoJZHVtcCgxMDAwMDApOwoJZHVtcCgxMDAwMDApOwoJZHVtcCgxMDAwMDAwKTsKCWR1bXAoMTAwMDAwMCk7CgoJcmV0dXJuIDA7Cn0KCg==