zapada

Aurel s-a pregătit pentru ninsoare, dar zăpada care s-a așezat aseară tot i-a dat bătăi de cap. Aleea pe care trebuie să o deszăpezească Aurel este formată din $n$ dale pătrate, pozițiile acestora fiind numerotate în ordine, de la stânga la dreapta, de la $1$ la $n$. Fiind un tip meticulos, înainte de a se apuca de treabă, Aurel a determinat cantitatea de zăpadă (exprimată în grame) care s-a așezat pe fiecare dintre cele $n$ dale și a notat cu $z_i$ cantitatea de zăpadă existentă pe dala $i$ ($1 \le i \le n$). Pentru a curăța aleea, el trebuie să mute toată zăpada de pe alee, în stânga sau în dreapta acesteia. Pentru simplitate, vom considera că zona din stânga aleii are poziția $0$, iar zona din dreapta aleii are poziția $n + 1$.

Pentru deszăpezire, Aurel a cumpărat $40$ de lopeți speciale, numerotate de la $0$ la $39$. Cu lopata $k$ ($0 \le k \le 39$) Aurel poate muta cel mult $2^k$ grame de zăpadă de pe dala pe care se află aceasta pe o poziție alăturată, la stânga sau la dreapta, deci de pe poziția $i$ ($1 \le i \le n$) pe poziția $i - 1$ sau pe poziția $i + 1$, pentru această acțiune consumând $k + 1$ calorii.

Pentru a fi eficient, Aurel a decis să împartă aleea în două zone. Prima zonă conține toate dalele situate pe poziții mai mici sau egale cu $x$, iar a doua zonă conține toate dalele de poziții strict mai mari decât $x$. El va folosi lopețile pentru a muta toată zăpada din prima zonă pe poziția $0$ și toată zăpada din a doua zonă pe poziția $n + 1$.

Cerință

Cunoscând numărul de dale și zăpada acumulată pe fiecare dală, scrieți un program care să rezolve următoarele cerințe:

1. cunoscând valoarea $x$, determinați numărul total minim de calorii consumate de Aurel pentru a deszăpezi aleea;
2. determinați valoarea $x$ pentru care numărul total de calorii consumate de Aurel pentru deszăpezirea aleii este minim; dacă există mai multe astfel de valori, să se determine cea mai mică dintre acestea.

Date de intrare

Fișierul de intrare zapada.in conține pe prima linie numărul natural $C$ reprezentând cerința care trebuie rezolvată ($1$ sau $2$). Pe a doua linie se află numărul natural $n$ reprezentând numărul de dale de pe alee. Pe a treia linie se află $n$ numere naturale separate prin câte-un spațiu $z_1, z_2, \dots z_n$, reprezentând cantitatea de zăpadă existentă pe fiecare dală. Dacă $C = 1$, atunci pe cea de-a patra linie se află numărul natural $x$.

Date de ieșire

Fișierul de ieșire zapada.out conține o singură linie pe care este scris răspunsul la cerința $C$.

Restricții și precizări

• $2 \le n \le 10^5$
• $1 \le z_i \le 10^6$, pentru orice $1 \le i \le n$
• $1 \le x < n$

Exemplul 1

zapada.in

1
4
1 3 1 3
2

zapada.out

10

Explicație

$C=1$. Există $4$ dale pe alee, iar $x$ este egal cu $2$, deci prima zonă este formată din dalele de pe pozițiile $1$ și $2$, iar a doua zonă din dalele de pe pozițiile $3$ și $4$. Pentru un consum minim de $10$ calorii, Aurel poate proceda astfel, pentru fiecare pas fiind indicată poziția de pe care este mutată zăpada, ce cantitate se mută și poziția pe care este mutată:
cu lopata $0$: $2 \xrightarrow{1gr} 1$; consum $1$
cu lopata $1$: $2 \xrightarrow{2gr} 1$; consum $2$
cu lopata $2$: $1 \xrightarrow{4gr} 0$; consum $3$
cu lopata $0$: $3 \xrightarrow{1gr} 4$; consum $1$
cu lopata $2$: $4 \xrightarrow{4gr} 5$; consum $3$
Calorii consumate în total $10$

Exemplul 2

zapada.in

2
4
1 4 4 1

zapada.out

1

Explicație

$C=2$. Dacă alegem $x=1$ putem deszăpezi aleea cu un consum total minim de $13$ calorii astfel:
cu lopata $0$: $1 \xrightarrow{1gr} 0$; consum $1$
cu lopata $2$: $2 \xrightarrow{4gr} 3$; consum $3$
cu lopata $3$: $3 \xrightarrow{8gr} 4$; consum $4$
cu lopata $4$: $4 \xrightarrow{9gr} 5$; consum $5$
Dacă alegem $x=3$ obținem același consum minim, dar $1$ este mai mic decât $3$.
Dacă alegem $x=2$ obținem un consum mai mare ($14$).

Exemplul 3

zapada.in

2
10
5 3 2 2 7 3 5 5 3 5

zapada.out

2

Explicație

$C=2$. Consumul total minim de calorii este $46$ și se obține pentru $x=2$ și $x=4$ ($2$ fiind minim).
Orice altă alegere pentru $x$ conduce la un consum de calorii mai mare.