Simulation - Info-Oltenia 2024 XI-XII | Centrat

Pentru un șir de $N$ numere întregi, se poate determina o poziție centrală astfel încât suma numerelor din stânga poziției să fie cât mai apropiată de suma celor din dreapta. Dacă numărul de pe poziția centrală este impar, atunci se adaugă $1$ la suma cea mai mică.

Se pot efectua operații pe termenii șirului de forma: $P\ V$. Termenul din șir de pe poziția $P$ va fi înlocuit cu numărul $V$.

Asupra șirului inițial se efectuează succesiv $T$ operații descrise mai sus. După fiecare operație se recalculează poziția centrală.

Cerință

Calculați poziția pentru cele $T$ șiruri derivate.

Date de intrare

Se vor citi din fișierul de intrare centrat.in următoarele date:

• pe prima linie un număr natural $N$, reprezentând lungimea șirului;
• pe a doua linie șirul inițial format din $N$ numere naturale;
• pe a treia linie un număr natural $T$, reprezentând numărul de operații efectuate;
• pe următoarele $T$ linii două numere $P_i$ și $V_i$, semnificând schimbarea numărului de pe poziția $P_i$ cu $V_i$.

Date de ieșire

În fișierul de ieșire centrat.out se vor găsi $T$ numere, câte unul pe fiecare linie, reprezentând pozițiile centrale ale celor $T$ șiruri modificate.

Restricții și precizări

• $1 \leq N, T \leq 100\ 000$;
• $1 \leq P_i \leq N$, $\forall\ 1 \leq i \leq T$;
• $1 \leq V_i \leq 1\ 000\ 000$, $\forall\ 1 \leq i \leq T$;
• Pentru $30\%$ din teste, $N \leq 100$, sau $N \leq 2\ 000$ și $T \leq 10\ 000$.
• Dacă sunt mai multe poziții centrale posibile, afișați-o pe cea mai mică.

Exemplu

centrat.in

5
4 1 3 9 1
2
4 2
1 10

centrat.out

2
2

Explicație

Șirul obținut după prima operație este 4 1 3 2 1, iar după a doua operație se obține șirul 10 1 3 2 1.

Pentru primul șir, diferența minimă este de $1$, obținută la poziția $2$. Suma din stânga poziției este $4$, iar cea din dreapta este $3+2+1=6$. Deoarece suma din stânga este mai mică și $1$ este număr impar, ea devine $4+1=5$.