Щоденний поділ
Оостенде — це довгий пляж на півночі Бельгії, де розташовані n хатинок уздовж прямої лінії. Відпочивальники можуть орендувати кімнату в одній з цих хатинок, щоб насолодитися відпусткою на пляжі разом з іншими гостями.
Щодня під час обіду приїжджає вантажівка з їжею, щоб пригостити гостей картоплею фрі. Вантажівка зупиняється перед однією з хатинок, і люди формують дві черги. Ті, хто живе в хатинках зліва від вантажівки, стають у ліву чергу, а ті, хто справа — у праву. Гості з хатинки, перед якою зупинилася вантажівка, діляться на дві групи: одна йде в ліву чергу, інша — в праву. Якщо кількість людей непарна, одна людина приєднується до черги з меншою кількістю людей, або вибирає випадкову чергу, якщо обидві черги однакові за довжиною. Вантажівка завжди зупиняється так, щоб різниця між кількістю людей у лівій і правій чергах була якомога меншою.
Щоночі кількість гостей в одній з хатинок змінюється. Чи можете ви допомогти вантажівці знайти найкраще місце для зупинки кожного дня?
Вхідні дані
Перший рядок містить два цілі числа n (1 ≤ n ≤ 10^5) — кількість хатинок і q (1 ≤ q ≤ 10^5) — кількість днів. Другий рядок містить n цілих чисел a[0], ..., a[n−1], де 1 ≤ a[i] ≤ 10^6 для 0 ≤ i < n, що представляють кількість людей у хатинці i. Далі йдуть q рядків з двома цілими числами i (0 ≤ i < n) і x (1 ≤ x ≤ 10^6). j-ий рядок вказує, що в день j кількість людей у хатинці i змінюється на x.
Вихідні дані
Виведіть q рядків — оптимальне положення вантажівки після кожної q-ої ночі. Якщо існує кілька оптимальних позицій, виведіть найменшу.