Задача V. Передовики производства

Автор:folklore   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

На секретном оборонном заводе трудятся N рабочих. Каждый рабочий характеризуется своей производительностью — целым числом. С течением времени производительность некоторых рабочих может увеличиваться или уменьшаться. Вам задано число M — количество изменений производительности. Для каждого изменения известен номер рабочего, изменившего свою производительность и значение, на которое он она изменилась. Величина изменения может быть как положительной, так и отрицательной. Для планирования будущих достижений руководству завода необходимо всегда знать наибольшую производительность, достигнутую рабочими в данный момент.

Формат входного файла

В первой строке входного файла содержатся целые числа N M, разделенные пробелами. Далее следуют N чисел Ai, обозначающих производительность i-рабочего. Завершают входной файл M пар чисел Numi Vali, обозначающие номер рабочего, производительность которого изменилась и величину изменения соответственно.

Формат выходного файла

В выходной файл необходимо вывести M чисел — после каждого изменения производительности необходимо вывести наибольшую производительность по заводу.

Ограничения

(1 ≤ N, M ≤ 100000, 1 ≤ Numi ≤ N, −1000 ≤ Vali, Ai ≤ 1000)

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 4
7 4 9 
2 3
1 4
2 10
2 -10
9
11
17
11

0.058s 0.008s 13