У Евгения есть массив a = a1, a2, ..., an, состоящий из n целых чисел. Каждое число ai равно или 1, или -1. Также есть m запросов:
Помогите Евгению, ответьте на все его запросы.
В первой строке записаны целые числа n и m (1 ≤ n, m ≤ 2·105). Во второй строке записаны n целых чисел a1, a2, ..., an (ai = -1, 1). В следующих m строках заданы запросы Евгения. В i-той строке записаны целые числа li, ri (1 ≤ li ≤ ri ≤ n).
Выведите m целых чисел — ответы на запросы Евгения в порядке их следования во входных данных.
2 3 1 -1 1 1 1 2 2 2
0 1 0
5 5 -1 1 1 1 -1 1 1 2 3 3 5 2 5 1 5
0 1 0 1 0
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач