Конвейер

Алексей и Аня играют в следующую игру. Аня на N карточках записывает по одному числу a_i. После чего карточки выкладываются в ряд. Алексей набирает себе числа по следующему правилу: берёт число, которое стоит на первом месте, затем берёт следующее первое встретившееся число строго большее предыдущего взятого и так далее. Например, если даны карточки с числами [2, 5, 3, 5, 6, 4, 1, 7, 5], то Алексей возьмёт следующие карточки [2, 5, 6, 7], итого у Алексея 4 карточки. После этого Алексей кладёт карточки на свои же места, а Аня стирает на одной из карточек число и пишет другое, больше на x. После Алексей снова набирает карточки по вышеописанному правилу.

Сколько карточек будет набирать Алексей после каждого изменения?

Входные данные

В первой строке входного файла INPUT.TXT находится натуральное число N – количество карточек (1 ≤ N ≤ 10⁵). Во второй строке даны N натуральных чисел a_i – числа на карточках (0 ≤ a_i ≤ 10⁹). В третьей строке число Q – количество изменений (1 ≤ Q ≤ 10⁵).

В следующих Q строках описаны изменения парой целых чисел p и x – Аня увеличивает a_p на x (1 ≤ p ≤ N, 0 ≤ x ≤ 10⁹).

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Пример

Автор задачи

Владимир Игоревич Лукьянчиков

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]