Задача E. Подарочный массив ≡

Условие

У программиста Германа сегодня день рождения. Друзья решили сделать ему тематический подарок: они подарили ему массив длиной n, состоящий из двоичных цифр. Подарок Герману очень понравился и он сразу стал с ним экспериментировать.

Он придумал следующую операцию: выбирается некоторый отрезок от l до r включительно и все цифры на нём инвертируются (цифры 0 заменяются на 1, а цифры 1 заменяются на 0). Данную операцию он выполнил q раз. В процессе таких операций он записывал на листочек, сколько цифр 1 получилось в массиве после каждой инверсии. После всех операций он пошел спать.

На утро Герман понял, что забыл закрыть окно на ночь и листочек со всеми его записями улетел. Он помнит лишь последовательность операций. Исходя из них, он просит Вас написать программу, которая определит, какое максимальное количество единиц было в массиве после выполнения некоторой операции в последовательности.

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

В первой строке записано число n — длина массива.

Во второй строке записано n цифр a_i — двоичные цифры в массиве.

В третьей строке записано число q — количество операций, которое проделал Герман.

В следующих q строках записано по два положительных числа l и r — отрезки, массива к которым применялась операция.

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

Выведите одно число — максимальное количество единиц в массиве.

Ограничения

1 ≤ n, q ≤ 10⁵

0 ≤ a_i ≤ 1

1 ≤ l ≤ r ≤ n

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

5
1 0 0 1 0
3
1 3
2 4
5 5

3