A permutation of size n is an array of size n such that each integer from 1 to n occurs exactly once in this array. An inversion in a permutation p is a pair of indices ( i , j ) such that i > j and a i < a j . For example, a permutation 4, 1, 3, 2 contains 4 inversions: (2, 1) , (3, 1) , (4, 1) , (4, 3) . You are given a permutation a of size n and m queries to it. Each query is represented by two indices l and r denoting that you have to reverse the segment l , r of the permutation. For example, if a = 1, 2, 3, 4 and a query l = 2 , r = 4 is applied, then the resulting permutation is 1, 4, 3, 2 . After each query you have to determine whether the number of inversions is odd or even. The first line contains one integer n ( 1 ≤ n ≤ 1500 ) — the size of the permutation. The second line contains n integers a 1 , a 2 , ..., a n ( 1 ≤ a i ≤ n ) — the elements of the permutation. These integers are pairwise distinct. The third line contains one integer m ( 1 ≤ m ≤ 2·10 5 ) — the number of queries to process. Then m lines follow, i -th line containing two integers l i , r i ( 1 ≤ l i ≤ r i ≤ n ) denoting that i -th query is to reverse a segment l i , r i of the permutation. All queries are performed one after another. Print m lines. i -th of them must be equal to odd if the number of inversions in the permutation after i -th query is odd, and even otherwise. The first example: after the first query a = 2, 1, 3 , inversion: (2, 1) ; after the second query a = 2, 3, 1 , inversions: (3, 1) , (3, 2) . The second example: a = 1, 2, 4, 3 , inversion: (4, 3) ; a = 3, 4, 2, 1 , inversions: (3, 1) , (4, 1) , (3, 2) , (4, 2) , (4, 3) ; a = 1, 2, 4, 3 , inversion: (4, 3) ; a = 1, 4, 2, 3 , inversions: (3, 2) , (4, 2) .