using namespace std;
typedef long long ll;
typedef vector<ll> vec;
const ll INF = (ll)1e18;
template<typename T>
ostream& operator <<(ostream& os, vector<T>& v) {
if(!v.empty()) {
os << v.front();
for(auto p = v.begin() + 1; p != v.end(); ++p) {
os << ',' << *p;
}
}
return os;
}
void turn(vector<ll>& a) {
ll s = a[0];
for(int k = 1; k < (int)a.size(); ++k) {
const ll e = a[k];
if(k % 2 == 0) {
a[k-1] = max(e, e - s);
s = max(s + e, e);
}
else {
a[k-1] = min(e, s);
s -= e;
}
}
a.back() = s;
}
bool is_invariant(const vector<ll>& a) {
for(int k = 0; k < (int)a.size() - 1; k += 2) {
if(a[k] > a[k+2] || a[k] > a[k+1])
return false;
}
return true;
}
ll state(const vector<ll>& a) {
ll s = 0;
for(int k = 0; k < (int)a.size(); ++k) {
s += a[k] * a[k];
}
return s;
}
vector<ll> init(int N) {
vector<ll> a(N + 1);
ll s = 290797;
for(int k = 0; k <= N; ++k) {
a[k] = s % 64 + 1;
s = s * s % 50515093;
}
return a;
}
ll sum_squares(const vector<ll>& a) {
ll s = 0;
for(int k = 0; k < (int)a.size(); k += 2)
s += a[k] * a[k];
return s;
}
int e426_naive(int N) {
const int t0 = timeGetTime();
vector<ll> a = init(N);
for(ll k = 0; !is_invariant(a); ++k) {
turn(a);
if(k % 1000 == 0)
cerr << k << " " << (timeGetTime() - t0) * 1e-3 << "sec" << endl;
}
return sum_squares(a);
}
class cTree {
public:
bool bleaf;
cTree *parent;
cTree *left;
cTree *right;
cTree *prev;
cTree *next;
ll val1;
ll val2;
ll a;
ll b;
ll kmax;
cTree(const vec& v, int first, int last, cTree *parent) {
this->parent = parent;
if(first == last - 2) {
bleaf = true;
val1 = v[first];
val2 = v[last];
update_mid(0, v[first+1]);
}
else {
bleaf = false;
const int mid = (last - first) / 4 * 2 + first;
left = new cTree(v, first, mid, this);
right = new cTree(v, mid, last, this);
kmax = min(left->kmax, right->kmax);
}
}
~cTree() {
if(!bleaf) {
delete left;
delete right;
}
}
void set_prev_next() {
if(!bleaf) {
left->set_prev_next();
auto left1 = left->rightmost();
auto right1 = right->leftmost();
left1->next = right1;
right1->prev = left1;
right->set_prev_next();
}
}
///// operation /////
ll proceed(ll k, ll s1) {
if(bleaf) {
const ll mid0 = mid(k - 1);
const ll s2 = val1 + max(0L, s1);
const ll e1 = min(mid0, s2);
const ll s3 = s2 - mid0;
const ll e2 = val2 - min(0L, s3);
const ll s4 = val2 + max(0L, s3);
ll e3;
if(next != NULL) {
const ll next_mid = next->mid(k - 1);
e3 = min(next_mid, s4);
}
else {
e3 = s4;
}
val1 = e1;
val2 = e3;
update_mid(k, e2);
if(prev != NULL && prev->val2 != e1) {
const ll prev_mid = prev->mid(k);
prev->val2 = e1;
prev->update_mid(k, prev_mid);
prev->parent->update_kmax();
}
return s3;
}
else {
if(s1 > 0 || left->kmax <= k) {
s1 = left->proceed(k, s1);
kmax = min(left->kmax, right->kmax);
}
if(s1 > 0 || right->kmax <= k) {
const ll s3 = right->proceed(k, s1);
kmax = min(left->kmax, right->kmax);
return s3;
}
else {
return 0;
}
}
}
void update_mid(ll k, ll mid) {
a = val2 - val1;
b = -k * a + mid;
if(val1 > mid)
kmax = k;
else if(a >= 0)
kmax = INF;
else
kmax = (b - val1) / -a + 1;
}
void update_kmax() {
ll new_kmax = min(left->kmax, right->kmax);
if(new_kmax != kmax) {
kmax = new_kmax;
if(parent != NULL)
parent->update_kmax();
}
}
///// attribute /////
ll mid(ll k) {
return a * k + b;
}
cTree *leftmost() {
if(bleaf)
return this;
else
return left->leftmost();
}
cTree *rightmost() {
if(bleaf)
return this;
else
return right->rightmost();
}
ll sum_squares() {
cTree *leaf = leftmost();
ll s = leaf->val1 * leaf->val1;
while(leaf != NULL) {
s += leaf->val2 * leaf->val2;
leaf = leaf->next;
}
return s;
}
};
cTree *make_tree(const vec& a) {
const int N = (int)a.size() - 1;
cTree *tree = new cTree(a, 0, N, NULL);
tree->set_prev_next();
tree->leftmost()->prev = NULL;
tree->rightmost()->next = NULL;
return tree;
}
void write_array(const vec& a, int k) {
stringstream ss;
ss << "result_" << k << ".txt" << endl;
// FILE *fp = fopen(ss.str().c_str(), "wt");
FILE *fp = fopen("bbbbbbbbb.txt", "wt");
if(fp == NULL)
exit(1);
fprintf(fp, "%d\n", k);
for(auto p = a.begin(); p != a.end(); ++p)
fprintf(fp, "%d\n", *p);
fclose(fp);
}
vector<ll> read_array(int N) {
FILE *fp = fopen("turn4040000.txt", "rt");
char buff[80];
fgets(buff, 80, fp);
vector<ll> a;
for(int k = 0; k < N; ++k) {
fgets(buff, 80, fp);
a.push_back(_atoi64(buff));
}
return a;
}
ll e426(int N) {
int t0 = timeGetTime();
vector<ll> a = read_array(N);
cTree *tree = make_tree(a);
t0 = timeGetTime();
ll k = 1;
int counter = 0;
cout << tree->kmax << endl;
while(tree->kmax != INF) {
tree->proceed(k, 0);
if(counter % 10000 == 0)
cerr << k << " " << tree->kmax << " " <<
(timeGetTime() - t0) * 1e-3 << "sec" << endl;
counter += 1;
k = max(k + 1, tree->kmax);
}
ll s = tree->sum_squares();
delete tree;
return s;
}
int main() {
const int t0 = timeGetTime();
const int N = (int)1e7;
// 10^5 -> 354377586
// cout << e426_naive(N) << endl;
cout << e426(N) << endl;
cerr << (timeGetTime() - t0) * 1e-3 << "sec" << endl;
}
