Задача F. Шпаргалки
Задачу добавил: alef
Успешно сдано решений: 5
Современные студенты и шпаргалки делают с использованием современных технологий. Спички, резинки, бумажная лента — это ж прошлый век. Почти каждый из однокурсников Николая подготовил свой "комплект" по каждому вопросу. И получилось это у всех по-разному. Так что на общем собрании группы решили "обменяться опытом", а Николай вызвался написать программу, которая упрощала бы работу с наборами шпаргалок.
Программа Николая отображает листочки со шпаргалками в "миниатюре", располагая их построчно. Все электронные версии "листочков" собраны в "репозиторий", и для каждого вопроса (№ j) можно выбрать любой "листочек" из "репозитория".
Однако оказалось, что представления о том, какого размера должна быть шпаргалка, у студентов различаются. И если высота "листочков" у всех была выбрана практически одинаковая, то ширина...
В общем, по мере пополнения "репозитория" программа Николая начала уж очень сильно подтормаживать в процессе перерисовки "миниатюр". Действительно, замена всего одного "листочка" на другой — другой ширины — могла привести к тому, что строка, в которой располагался этот "листочек", переставала умещаться в границах окна и разбиение на строки полностью менялось.
Чтобы улучшить работу программы, Николай для начала хочет научиться определять, сколько строчек потребуется для вывода всех "миниатюр", после того, как ширина одной из них изменилась.
Ваша задача — помочь ему в этом.
Формат входного файла input.txt
Первая строка — целые числа N, L и Q (1 <= N, Q <= 10^5; 1 <= L <= 10^4) через пробел — количество отображаемых миниатюр, длина строки, количество запросов на изменение ширины очередной миниатюры.
Вторая строка — N целых чисел W1, W2, ..., WN (1 <= Wj <= L, j = 1, 2, ..., N) через пробел — исходная ширина каждой из миниатюр
Следующие Q строк содержат по два целых числа: номер миниатюры и ее новую ширину.
Формат выходного файла output.txt
Q+1 строка, в каждой из которых записано количество строк, необходимых для размещения миниатюр.
В первой строке — количество строк до каких-либо изменений
Пример входного файла
3 9 3
5 5 5
2 3
1 1
1 8
Пример выходного файла
3
2
1
2