На первой строке длина массива n ( 1 ≤ n ≤ 300 000 ). На второй строке n целых чисел от 0 до 10 ⁹ { - }1 . На третьей строке количество запросов q ( 1 ≤ q ≤ 300 000 ). Следующие q строк содержат описание запросов, по одному на строке. Каждый запрос задаётся парой целых чисел l , r ( 1 ≤ l ≤ r ≤ n ).