Задача 8H. Интересные моменты

Автор:Завгороднев А.А.   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

Пётр решил приукрасить свою страницу во ВКонтакте. А именно привести в порядок свои фотографии. Так получилось, что некоторые фотографии у него интересные, а некоторые не очень. И вот Петя решил испробовать методику интересных моментов.

Интересный момент возникает, когда пара интересных фотографий идут друг за другом. То есть, например, трое подряд идущих интересных фотографий создадут 2 интересных момента.

И вот Пётр хочет, чтобы его страница получилась сбалансированной, поэтому просит вас помочь найти количество интересных моментов в его странице, начиная с фотографии номер l до фотографии с номером r.

Пётр ещё в процессе выкладывания фотографий, поэтому иногда он добавляет или удаляет некоторые из них. После каждого из таких его действий нумерация всех фотографий обновляется.

Формат входных данных

В первой строке входных данных располагается число n — количество уже имеющихся фотографий на странице Петра в ВК. (1 ≤ n ≤ 105).

Во второй строке находится последовательность из n нулей и единиц, в которой если на i-й позиции находится единица, то фотография с номером i интересная. И не интересная, если i-й позиции находится ноль.

Далее располагается число q — количество действий Петра (0 ≤ q ≤ 105).

В следующих q строках находится описание действий Петра:

Гарантируется, что все заданные номера фотографий существуют на странице (за исключением p =  − 1, но этот случай описан выше).

Нумерация фотографий начинается с нуля.

Формат выходных данных

Для каждого вопроса Петра через пробел выведите количество интересных моментов на странице, начиная с фотографии l и заканчивая фотографией r включительно.


Объяснение примера:

Сначала страница выглядела так: 0111011

Далее тут (0111011) три интересных момента, между 1 и 2 фото, между 2 и 3 фото и между 5 и 6 фото.

Далее тут 01 (11011) два интересных момента.

После этого страница стала выглядеть так: 01101011.

Далее тут (01101011) два интересных момента.

После этого страница стала выглядеть так: 0110111.

Далее тут 0(110111) три интересных момента.

После этого страница стала выглядеть так: 011111.

Далее тут (011111) 4 интересных момента.

После этого страница стала выглядеть так: 11111.

И тут (11111) также 4 интересных момента.

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

Стандартный вход Стандартный выход
1
7
0111011
10
q 0 6
q 2 6
i 2 0
q 0 7
d 5
q 1 6
d 3
q 0 5
d 0
q 0 4
3 2 2 3 4 4 

0.064s 0.014s 15