Ежедневное деление
Оостенде - очень длинный пляж, расположенный на севере Бельгии. На этом пляже находятся n хижин, расположенных вдоль прямой линии. Люди могут снять комнату в одной из этих хижин, чтобы провести отпуск на пляже вместе с другими жильцами.
Каждый день во время обеда едет грузовик с едой, чтобы подать картофель фри гостям. Грузовик припаркуется перед одной из хижин, и люди сформируют две очереди. Люди, находящиеся в хижинах слева от продовольственного грузовика, будут стоять в очереди слева, а люди справа от продовольственного грузовика будут стоять в очереди справа. Люди, стоящие в хижине перед грузовиком с едой, разделят свою группу пополам: одна половина пойдет в левую очередь, а другая половина - в правую. Если это нечетное количество людей, оставшийся человек пойдет в очередь с меньшим количеством людей, или выберет очередь случайным образом, если они имеют одинаковую длину. Грузовик с едой всегда будет располагаться так, чтобы разница между количеством людей в левой очереди и количеством людей в правой очереди была как можно меньше.
Каждую ночь количество гостей в одной из хижин меняется. Можете ли Вы помочь фургону найти лучшую позицию на каждый день?
Входные данные
Первая строка содержит два целых числа n (1 ≤ n ≤ 10^5) - количество хижин и q (1 ≤ q ≤ 10^5) - количество дней. Вторая строка содержит n целых чисел a[0], ..., a[n−1] удовлетворяющих 1 ≤ a[i] ≤ 10^6 for 0 ≤ i < n, где a[i] - число людей в хижине i. Далее следуют q строк с двумя целыми числами i (0 ≤ i < n) и x (1 ≤ x ≤ 10^6). j-ая строка указывает что в день j количество людей в хижине i изменяется на x.
Выходные данные
Выведите q строк - оптимальное положение грузовика после каждой q-ой ночи. Если существует несколько оптимальных позиций, выведите наименьшую.