h2. Restricţii si precizări

* $N ≤ 1000000$

* $N ≤ 1.000.000$

* $T ≤ 10^9^$
* $A{~i~} ≤ 10^9^, 1 ≤ i ≤ N$
* $A{~i~} ≤ A{~i+1~}, 1 ≤ i ≤ N - 1$

h2. Subtask-uri
* *$Subtaskul 1 (20 de puncte):$* $N ≤ 15$

* *$Subtaskul 2 (20 de puncte):$* $N ≤ 200 000, A{~i~} = A{~N~} pentru 1 ≤ i ≤ N$
* *$Subtaskul 3 (30 de puncte):$* $N ≤ 200 000$

* *$Subtaskul 2 (20 de puncte):$* $N ≤ 200.000, A{~i~} = A{~N~} pentru 1 ≤ i ≤ N$
* *$Subtaskul 3 (30 de puncte):$* $N ≤ 200.000$

* *$Subtaskul 4 (30 de puncte):$* restricţiile iniţiale
h2. Exemplu