| Автор: | Иван Кобец, Артём Завгороднев | Ограничение времени: | 2 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
| Выходной файл: | Стандартный выход |
У программиста Германа сегодня день рождения. Друзья решили сделать ему тематический подарок: они подарили ему массив длиной n, состоящий из двоичных цифр. Подарок Герману очень понравился и он сразу стал с ним экспериментировать.
Он придумал следующую операцию: выбирается некоторый отрезок от l до r включительно и все цифры на нём инвертируются (цифры 0 заменяются на 1, а цифры 1 заменяются на 0). Данную операцию он выполнил q раз. В процессе таких операций он записывал на листочек, сколько цифр 1 получилось в массиве после каждой инверсии. После всех операций он пошел спать.
На утро Герман понял, что забыл закрыть окно на ночь и листочек со всеми его записями улетел. Он помнит лишь последовательность операций. Исходя из них, он просит Вас написать программу, которая определит, какое максимальное количество единиц было в массиве после выполнения некоторой операции в последовательности.
В первой строке записано число n — длина массива.
Во второй строке записано n цифр ai — двоичные цифры в массиве.
В третьей строке записано число q — количество операций, которое проделал Герман.
В следующих q строках записано по два положительных числа l и r — отрезки, массива к которым применялась операция.
Выведите одно число — максимальное количество единиц в массиве.
1 ≤ n, q ≤ 105
0 ≤ ai ≤ 1
1 ≤ l ≤ r ≤ n
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|