Fişierul intrare/ieşire:	veverite.in, veverite.out	Sursă	Junior Challenge 2021
Autor	Alexandru Luchianov	Adăugată de	Comisia •jc2021
Timp execuţie pe test	0.5 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Veverite

Pentru că Phineas şi Ferb s-au hotărât să instaureze viarna în orasul Danville, veveriţele s-au decis în sfârşit să o lase în pace pe Candace şi vor să îşi facă provizii de ghinde.

Iniţial veveriţele au un număr X de ghinde. Veveriţele vor colecta ghinde pe parcursul a N zile, in ziua i copacul din curtea familiei Flynn-Fletcher va avea A_i ghinde.

Veveriţele au un mod interesant de a-şi aduna ghinde. Acestea sunt fericite dacă în fiecare zi numărul lor de ghinde este mai mare sau egal ca numărul de ghinde care se află în ziua respectivă în copac.
La finalul fiecărei zile, acestea pot să-şi adune la colecţie toate ghindele care au fost în copac în ziua aceea. (Mai întâi trebuie să se respecte condiţia, apoi pot să adune ghindele)

Pentru că veveriţele ştiu cât de des Phineas şi Ferb observă dispariţia lui Perry ornitorincul, nu ar vrea să riste ca aceştia să observe şi ghindele lipsă din copac. Prin urmare, vor să minimizeze numărul de zile în care le fură din copac.

Pentru Q scenarii posibile în care se dă numărul iniţial de ghinde pe care îl au veveriţele, se cere numărul minim de zile în care veveriţele trebuie să fure ghindele din copac pentru a se respecta condiţiile, sau să spuneţi dacă acest lucru nu este posibil.

Date de intrare

Fişierul de intrare veverite.in va conţine pe prima linie două numere N (numarul de zile) şi Q (numărul de scenarii de test). A doua linie a fişierului conţine N numere separate prin câte un spaţiu reprezentând numărul de ghinde din fiecare zi. A treia linie contine Q numere separate prin câte un spaţiu care reprezintă numărul iniţial de ghinde.

Date de ieşire

În fişierul de ieşire veverite.out se vor afla Q numere separate prin câte un spaţiu reprezentând răspunsurile pentru fiecare scenariu. Dacă un scenariu nu se poate realiza, pentru acesta se va afişa -1.

Restricţii

• 1 ≤ N, Q ≤ 10⁵
• 1 ≤ A_i ≤ 10⁹
• A_i ≤ A_i+1 pentru 1 ≤ i ≤ N - 1

Subtaskuri

• Subtaskul 1 (20 de puncte): N,Q ≤ 2000
• Subtaskul 2 (20 de puncte): A_i ≤ 100, pentru 1 ≤ i ≤ N, N,Q ≤ 10⁵
• Subtaskul 3 (60 de puncte): restricţiile iniţiale

Exemplu

Explicaţie

Pentru primul scenariu, există mai multe variante pentru a obţine minimul. O variantă posibilă este să luăm ghindele din zilele 2,7 şi 8.
Numărul de ghinde pe parcursul celor N zile va fi: 5 8 8 8 8 8 15 25 25 25.

Pentru al doilea scenariu, numărul iniţial de ghinde este mai mic decât numărul de ghinde din copac din prima zi, deci nu avem soluţie.

Cum se trimit solutii?