MinimizeSum

Fie un șir $v_1, v_2, \dots, v_N$ de numere întregi. Operația magică constă în executarea următorilor pași:

• Se selectează o poziție $i$, $1 < i < N$.
• $v_i$ își modifică valoarea în $v_{i−1} + v_{i+1} − v_i$.

Aveți posibilitatea de a efectua operația magică de oricâte ori doriți.

Cerință

Scopul vostru este să transformați șirul inițial într-un șir cu suma elementelor cât mai mică posibil. Fie $S$ această sumă, iar $K$ numărul minim de aplicații a operației magice pentru a ajunge la un șir cu suma $S$.

Date de intrare

Prima linie conține numărul $P$ ($1$ sau $2$) care indică cerința care trebuie rezolvată. Pe a doua linie se află numărul natural $N$ reprezentând lungimea șirului. Pe a treia linie se vor afla $N$ numere întregi separate printr-un spațiu, valorile inițiale ale șirului $v$.

Date de ieșire

Fișierul de ieșire va conține exact un număr întreg. Dacă $P = 1$, acest număr trebuie să fie $S$ (suma minimă care se poate obține), iar dacă $P = 2$, trebuie să se afișeze $K$ (numărul minim de operații magice pentru a obține suma $S$).

Restricții și precizări

• $1 \leq N \leq 500 \ 000$
• $−10^{12} \leq v_i \leq 10^{12}$
• Se garantează că $S$ și $K$ pot fi reprezentate pe tipuri de date întregi pe $64$ de biți cu semn.

Exemplul 1

minimizesum.in

1
5
0 6 14 9 9

minimizesum.out

0

Exemplul 2

minimizesum.in

2
5
0 6 14 9 9

minimizesum.out

4

Explicație

În primele 2 exemple operația magică se poate aplica succesiv pe pozițiile $3$, $2$, $4$, $3$:
$[0, 6, 14, 9, 9] \rightarrow [0, 6, 1, 9, 9]$ $\rightarrow [0,−5, 1, 9, 9] \rightarrow$ $[0,−5, 1, 1, 9] \rightarrow [0,−5,−5, 1, 9]$

Obținem astfel în $4$ operații magice un șir cu suma $0 + (−5) + (−5) + 1 + 9 = 0$. Nu se poate obține o sumă mai mică indiferent de numărul de aplicări al operației magice.

Exemplul 3

minimizesum.in

1
15
21 19 14 9 8 5 5 4 3 3 7 13 19 28 37

minimizesum.out

184

Exemplul 4

minimizesum.in

2
15
21 19 14 9 8 5 5 4 3 3 7 13 19 28 37

minimizesum.out

6

Explicație

În exemplele 3 și 4, operația magică se poate aplica succesiv pe pozițiile $7$, $8$, $5$, $2$, $3$, $4$. Șirul final cu suma $184$ va fi:
$[21, 16, 11, 8, 6, 5, 4, 3, 3, 3, 7, 13, 19, 28, 37]$

Exemplul 5

minimizesum.in

1
25
139 101 61 17 -18 -54 -88 -119 -152 -182 -211 -238 -264 -276 -278 -276 -267 -245 -214 -178 -140 -95 -48 0 50

minimizesum.out

-2990

Exemplul 6

minimizesum.in

2
25
139 101 61 17 -18 -54 -88 -119 -152 -182 -211 -238 -264 -276 -278 -276 -267 -245 -214 -178 -140 -95 -48 0 50

minimizesum.out

5

Explicație

În ultimele 2 exemple operația magică se poate aplica succesiv pe pozițiile $3$, $2$, $3$, $8$, $5$.