Задача №112772. Ремонт асфальта
Улица М. города Д. печально известна среди местных жителей качеством дорожного покрытия. В этом тяжело винить ремонтные службы: пожалуй, они следят за этой улицей даже слишком тщательно. Проблема в том, что каждый без исключения ремонт улицы выглядит следующим образом: бригада рабочих выбирает некоторый участок улицы единичной длины и меняет асфальт только на нём, причём тип асфальта на этом участке в результате может отличаться от типов асфальта на других участках, что, разумеется, усложняет проезд по улице.
Вы, как коренной житель города Д. и программист по призванию, решили использовать свои профессиональные навыки на благо общества и облегчить жизнь своим соседям по улице \(М\). А именно, вы решили создать сайт, содержащий актуальную информацию о непроходимости улицы. Прежде всего, вы заметили, что улица разбита на N идущих друг за другом участков единичной длины. По странному совпадению бригада рабочих всегда выбирает для ремонта ровно один из таких участков и целиком меняет тип асфальта на нём. Затем вы пронумеровали эти участки от 1 до \(N\) и собрали информацию о типе асфальта на каждом из участков — числа \(t_1, t_2, ... , t_N\) (\(t_i\) — номер типа асфальта на \(i\)-м участке, согласно Государственному реестру дорожных покрытий). Наконец, вы определили непроходимость улицы как минимальное количество непрерывных непересекающихся отрезков c одинаковым типом асфальта, на которые она разбивается. Например, непроходимость улицы 110111 равна \(3\), потому что она состоит из трёх участков 11, 0 и 111, а идеальная улица 2222 имеет непроходимость, равную \(1\).
Казалось бы, достаточно вычислить и разместить на сайте текущую величину непроходимости улицы, и жители будут довольны? К сожалению, асфальт меняют довольно часто, и вам не хочется каждый раз выходить на улицу и заново собирать данные. Поэтому вы дали возможность жителям сообщать на вашем сайте об обновлении дорожного покрытия. Дело осталось за малым — научиться обновлять после каждого такого сообщения актуальную величину непроходимости улицы.
Первая строка входного файла содержит единственное натуральное число \(N\) — количество участков дороги \((1 \le N \le 100 000)\). Следующая строка содержит \(N\) целых чисел \(t_1, t_2, ... , t_N\) — исходные типы асфальта участков дороги \((|t_i | \le 10^9)\).
Третья строка содержит единственное натуральное число \(Q\) — количество сообщений от жителей об обновлении дорожного покрытия \((1 \le Q \le 100 000)\). Каждая из следующих \(Q\) строк содержит очередное сообщение.
\(i\)-е сообщение представляет собой пару целых чисел \(p_i\) , \(c_i\) — номер ремонтируемого участка дороги и новый номер типа асфальта на этом участке \((1 \le p_i \le N, |c_i | \le 10^9)\). Участки дороги нумеруются от 1 до \(N\) в порядке задания их исходного типа асфальта во второй строке входного файла.
Выведите \(Q\) строк. \(i\)-я строка (\(1 \le i \le Q\)) должна содержать единственное целое число — величину непроходимости улицы после первых \(i\) обновлений дорожного покрытия.
Рассмотрим подробнее второй тестовый пример. Изначально улица 1123221 состоит из 5 отрезков с одинаковым типом асфальта: 11, 2, 3, 22, 1 и, соответственно, имеет непроходимость, равную 5 (её не нужно выводить в выходной файл).
После первого ремонта улица станет выглядеть как 1223221 и всё ещё будет состоять из 5 участков, но других: 1, 22, 3, 22, 1. Поэтому её непроходимость равна 5, и первое число в выходном файле равно 5.
После второго ремонта улица будет состоять из 3 участков: 1, 22222, 1, так что второе число в выходном файле — 3.
После третьего ремонта получим 4 участка: 1, 2222, 9, 1, соответственно, третье и последнее число в выходном файле — 4.
Тесты к этой задаче состоят из трёх групп. Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
5 2 2 2 2 2 5 1 2 2 3 4 3 3 1 3 3
1 3 5 5 3
7 1 1 2 3 2 2 1 3 2 2 4 2 6 9
5 3 4