Плакаты
(Время: 8 сек. Память: 256 Мб Сложность: 74%)
Друзья готовятся встретить национальную команду, возвращающуюся с международной олимпиады по информатике. Для этого они подготовили множество красочных плакатов. Осталось только продумать детали поздравления.
Для того, чтобы приветствовать команду, n друзей встанут в круг. Пронумеруем их от 1 до n в
порядке их расположения по кругу. Таким образом, для всех i от 1 до n − 1 друзья с номерами i и
i + 1 стоят рядом, также рядом стоят друзья с номерами n и 1. У каждого из друзей есть плакат.
Каждый плакат характеризуется своей красочностью — целым неотрицательным числом. Плакат
у друга с номером i имеет красочность ai.
Когда поздравление начнётся, некоторые из друзей поднимут свои плакаты и будут показывать
их команде. Для того, чтобы члены команды не растерялись и смогли рассмотреть все плакаты, не
должно быть четырёх или более стоящих подряд друзей с поднятым плакатом.
Друзья планируют изменять плакаты в процессе встречи. Всего будет внесено q изменений в
плакаты. После i-го из них плакат друга с номером pi будет иметь красочность vi. После каждого
из изменений друзья хотят определить, какую максимальную суммарную красочность могут иметь
поднятые плакаты, если нельзя нарушать установленное ограничение.
Требуется написать программу, которая по заданной начальной красочности плакатов и последовательности их изменений определяет в начале, а также после каждого изменения, какой максимальной суммарной красочности поднятых плакатов можно добиться, не нарушая условие, что
поднято не более трёх плакатов подряд.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число n (4 ≤ n ≤ 40 000) — количество друзей.
Вторая строка содержит n целых чисел ai (0 ≤ ai ≤ 109) — исходные значения красочности
плакатов у друзей.
Третья строка содержит одно целое число q (0 ≤ q ≤ 40 000) — количество изменений плакатов,
которые вносили друзья.
Каждая из следующих q строк содержит два целых числа pi и vi (1 ≤ pi ≤ n; 0 ≤ vi ≤ 109) — номер друга, плакат которого изменился, и новая красочность этого плаката
Выходные данные
В выходной файл OUTPUT.TXT выведите q + 1 число. Перед первым изменением, а также после каждого изменения плакатов
выведите одно целое число — максимальное суммарное значение красочности поднятых плакатов,
если нельзя поднимать больше трёх плакатов подряд.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 6
1 2 3 4 5 6
2
6 0
2 5 | 17
13
15 |
Пояснение к примеру
Перед первым изменением плакаты следует поднять друзьям с номерами 2, 4, 5, 6. Суммарная
красочность поднятых плакатов будет равняться 17.
После первого изменения плакат друга с номером 6 имеет красочность 0. Теперь плакаты следует
поднять друзьям с номерами 1, 3, 4, 5. Суммарная красочность будет равняться 13.
После второго изменения плакат друга с номером 2 имеет красочность 5. Плакаты следует поднять друзьям с номерами 1, 2, 4, 5. Суммарная красочность будет равняться 15.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|