Fișierul intrare/ieșire	cartita.in, cartita.out	Sursă	OSEPI 2021 baraj gimnaziu
Autor	Dana Lica	Adăugată de	Mircea Rebengiuc • mircea_007
Timp de execuție pe test	0.2 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	3.75

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Cârtița (baraj gimnaziu)

În grădina lui Macarie există un șir de N morcovi, numerotați de la 1 la N. Ca să știe unde sunt plantați, Macarie a făcut câte o grămăjoară de pământ în dreptul fiecărui morcov și a notat înălțimea fiecăreia exprimată în centimetri. Astfel morcovul i are în dreptul său o grămăjoară de pământ cu înălțimea de
h[i] centimetri. O cârtiță neastâmpărată sapă galerii subterane pe sub morcovii lui Macarie. Când sapă o galerie către un morcov, tot pământul rezultat îl scoate afară modificând astfel înălțimea grămăjoarei corespunzătoare acelui morcov, dar și ale celorlalți morcovi din grădină. Dacă în urma săpării unei galerii către morcovul de pe poziția pos înălțimea grămăjoarei lui a crescut cu x centimetri, atunci înălțimile grămăjoarelor tuturor morcovilor se modifică după următoarea regulă ce depinde de un număr K:

• înălțimea grămăjoarei morcovului pos − 1 se modifică cu x − K centimetri iar a morcovului pos + 1 cu x + K centimetri,
• înălțimile gramăjoarelor morcovilor pos − 2 și pos + 2 se modifică cu x − 2 · K respectiv x + 2 · K centimetri
• În caz general, înălțimea se modifică după următoarele reguli pentru fiecare morcov din grădină:
  • Înălțimea h[pos − i] devine h[pos − i] + x − i · K, pentru fiecare i, 1 ≤ i ≤ pos − 1
  • Înălțimea h[pos + i] devine h[pos + i] + x + i · K, pentru fiecare i, 1 ≤ i ≤ N − pos

Cerință

Se cunosc înălțimile inițiale ale tuturor celor N grămăjoare și cele U modificări făcute de cârtiță asupra înălțimilor grămăjoarelor de pământ ale morcovilor.

Știm că în cadrul unei secvențe continue de morcovi cel mai tentant pentru cârtiță este morcovul cu cea mai mică înălțime a grămăjoarei de pământ.

Ajutați-l pe Macarie să identifice înălțimea grămăjoarei celui mai tentant morcov, pentru mai multe intervale date, după efectuarea tuturor modificărilor realizate de cârtiță.

Date de intrare

Fișierul de intrare cartita.in ...

Date de ieșire

În fișierul de ieșire cartita.out ...

Restricții

• ... ≤ ... ≤ ...

Exemplu

Explicație

...