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 𝑛 dale pătrate, pozițiile acestora fiind numerotate în ordine, de la stânga la dreapta, de la 1 la 𝑛. 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 𝑛 dale și a notat cu z[𝑖] cantitatea de zăpadă existentă pe dala 𝑖 (1 ≤ 𝑖 ≤ 𝑛). 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 𝑛 + 1.

Pentru deszăpezire, Aurel a cumpărat 40 de lopeți speciale, numerotate de la 0 la 39. Cu lopata 𝑘 (0 ≤ 𝑘 ≤ 39) Aurel poate muta cel mult 2𝑘 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 𝑖 (1 ≤ 𝑖 ≤ 𝑛) pe poziția 𝑖 − 1 sau pe poziția 𝑖 + 1, pentru această acțiune consumând 𝑘 + 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 𝑥, iar a doua zonă conține toate dalele de poziții strict mai mari decât 𝑥. 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 𝑛 + 1.

Cerința

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 𝑥, determinați numărul total minim de calorii consumate de Aurel pentru a deszăpezi aleea;
2. determinați valoarea 𝑥 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 zapada1.in conține pe prima linie numărul natural 𝐶 reprezentând cerința care trebuie rezolvată (1 sau 2). Pe a doua linie se află numărul natural 𝑛 reprezentând numărul de dale de pe alee. Pe a treia linie se află 𝑛 numere naturale separate prin câte-un spațiu z[1], z[2] , …, z[𝑛] , reprezentând cantitatea de zăpadă existentă pe fiecare dală. Dacă 𝐶 = 1, atunci pe cea de-a patra linie se află numărul natural 𝑥.

Date de ieșire

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

Restricții și precizări

• 2 ≤ 𝑛 ≤ 105
• 1 ≤ z[𝑖] ≤ 106, pentru orice 1 ≤ 𝑖 ≤ 𝑛
• 1 ≤ 𝑥 < 𝑛

Subtaskuri

• 𝐶 = 1
• 𝐶 = 2, 2 ≤ 𝑛 ≤ 1000
• 𝐶 = 2, 1000 < 𝑛 ≤ 50 000
• 𝐶 = 2, fără restricții suplimentare

Exemplul 1

zapada1.in

1
4
1 3 1 3
2

zapada1.out

10

Explicație

C=1. Există 4 dale pe alee, iar x este egal cu 2, deci prima zona 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

zapada1.in

2
4
1 4 4 1

zapada1.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

zapada1.in

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

zapada1.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.