B'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, xe2 x80 x89j) such that i xe2 x80 x89> xe2 x80 x89j and ai xe2 x80 x89< xe2 x80 x89aj. For example, a permutation [4, xe2 x80 x891, xe2 x80 x893, xe2 x80 x892] contains 4 inversions: (2, xe2 x80 x891), (3, xe2 x80 x891), (4, xe2 x80 x891), (4, xe2 x80 x893). 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, xe2 x80 x89r] of the permutation. For example, if a xe2 x80 x89= xe2 x80 x89[1, xe2 x80 x892, xe2 x80 x893, xe2 x80 x894] and a query l xe2 x80 x89= xe2 x80 x892, r xe2 x80 x89= xe2 x80 x894 is applied, then the resulting permutation is [1, xe2 x80 x894, xe2 x80 x893, xe2 x80 x892]. After each query you have to determine whether the number of inversions is odd or even. The first line contains one integer n (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n xe2 x80 x89 xe2 x89 xa4 xe2 x80 x891500) -- the size of the permutation. The second line contains n integers a1, a2, ..., an (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89ai xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n) -- the elements of the permutation. These integers are pairwise distinct. The third line contains one integer m (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89m xe2 x80 x89 xe2 x89 xa4 xe2 x80 x892 xc2 xb7105) -- the number of queries to process. Then m lines follow, i-th line containing two integers li, ri (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89li xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89ri xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n) denoting that i-th query is to reverse a segment [li, xe2 x80 x89ri] 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: The second example: '...