Zadanie

Kopčeky zmrzliny

Počet bodov: 80

Vojtov obľúbený zmrzlinár má nezvyčajný spôsob podávania zmrzliny. Všetky nádoby so zmrzlinou sú uložené v jednom rade, každá s inou príchuťou. Nádoby sú očíslované \(1, 2, \ldots, n\) zľava doprava. Každý zákazník si môže vybrať jednu nádobu (s číslom \(i\)) a dostane kornútok so zmrzlinou z každej nádoby od \(1\) do \(i\).

Vojto má zmrzlinu veľmi rád, ale musí priznať, že niektoré príchuťe sú lepšie ako iné. Každej príchuti priradil kladné celé číslo ktoré predstavuje chutnosť. Chutnosť zmrzliny v nádobe s číslom \(i\) je \(a_i\). Chutnosť kornútku je priemer chutností všetkých príchutí v ňom.

Občas sa nejaká príchuť minie a zmrzlinár naplní nádobu na jej mieste inou príchuťou. Po každej zmene by Vojto chcel vedieť, aká je najväčšia možná chutnosť kornútku. Môžete mu pomôcť a povedať ktorú nádobu si má vybrať, aby dostal taký kornútok?

Vstup a výstup

Na prvom riadku sú dve celé čísla \(n\) a \(q\) (\(1 \leq n \leq 100\,000, 1 \leq q \leq 100\,000\)), počet nádob a počet zmien príchute. Na nasledujúcom riadku je \(n\) čísel \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 10^8\)) – chutnosť príchutí v nádobách.

Na každom z nasledujúcich \(q\) riadkov sú dve čísla \(p_j\) a \(b_j\) (\(1 \leq p_j \leq n, 1 \leq b_j \leq 10^8\)) – chutnosť novej zmrzliny v nádobe \(p_j\) je \(b_j\).

Po každej zmene príchute, vypíšte jedno číslo – číslo nádoby, ktorú si má Vojto vybrať, ak chce kornútok s najväčšou možnou chutnosťou. Ak je takých viac, vypíšte tú s naj menším číslom.

V prvej sade (10 bodov) platí \(n \leq 100, q \leq 100, a_i, b_j \leq 10^4\). V druhej a tretej sade (20 bodov) platí \(n \leq 1000, q \leq 1000\). V štvrtej až ôsmej sadách (50 bodov) niesu žiadne ďalšie obmedzenia.

Príklad

Input:

3 2
3 2 5
2 1
2 3

Output:

1
3

Po prvej zmene sú chutnosti: \([3, 1, 5]\). Chutnosti kornútkov sú: \([3, 2, 3]\), čiže Vojto dostane najlepší kornútok ak si zvolí prvú alebo tretiu nádobu, preto by si mal zvoliť prvú. Po druhej zmene sú chutnosti v nádobách: \([3, 3, 5]\), zatiaľ čo chutnosti kornútkov sú: \([3, 3, \frac{11}{3}]\). Vojto by si mal vybrať poslednú nádobu.