CF911D.Inversion Counting

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.

大小为 $n$ 的排列是一个长度为 $n$ 的数组，其中每个从 $1$ 到 $n$ 的整数恰好出现一次。排列 $p$ 中的一个逆序对是指一对下标 $(i,\,j)$，满足 $i > j$ 且 $a_i < a_j$。例如，排列 $[4,\,1,\,3,\,2]$ 包含 $4$ 个逆序对：$(2,\,1)$、$(3,\,1)$、$(4,\,1)$、$(4,\,3)$。

给定一个大小为 $n$ 的排列 $a$ 以及 $m$ 个对该排列的查询。每个查询由两个下标 $l$ 和 $r$ 表示，表示你需要将排列中区间 $[l,\,r]$ 内的元素进行翻转。例如，若 $a = [1,\,2,\,3,\,4]$，并执行查询 $l = 2,\,r = 4$，则翻转后得到的排列为 $[1,\,4,\,3,\,2]$。

每次查询后，你都需要判断当前排列中逆序对的总数是奇数还是偶数。

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·105) — 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.

第一行包含一个整数 $n$（$1 \leq n \leq 1500$）—— 排列的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq n$）—— 排列的元素。这些整数两两不同。

第三行包含一个整数 $m$（$1 \leq m \leq 2 \cdot 10^5$）—— 需要处理的查询数量。

接下来是 $m$ 行，其中第 $i$ 行包含两个整数 $l_i, r_i$（$1 \leq l_i \leq r_i \leq n$），表示第 $i$ 个查询要求将排列中区间 $[l_i,\, r_i]$ 内的元素进行翻转。所有查询按顺序依次执行。

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.

输出 $m$ 行。其中第 $i$ 行应为 odd（奇数），如果第 $i$ 次查询后的排列中逆序对数量为奇数；否则为 even（偶数）。

The first example:

1. after the first query a = [2, 1, 3], inversion: (2, 1);
2. after the second query a = [2, 3, 1], inversions: (3, 1), (3, 2).

The second example:

1. a = [1, 2, 4, 3], inversion: (4, 3);
2. a = [3, 4, 2, 1], inversions: (3, 1), (4, 1), (3, 2), (4, 2), (4, 3);
3. a = [1, 2, 4, 3], inversion: (4, 3);
4. a = [1, 4, 2, 3], inversions: (3, 2), (4, 2).

第一个示例：

1. 第一次查询后，$a = [2, 1, 3]$，逆序对为：$(2, 1)$；
2. 第二次查询后，$a = [2, 3, 1]$，逆序对为：$(3, 1), (3, 2)$。

第二个示例：

1. $a = [1, 2, 4, 3]$，逆序对为：$(4, 3)$；
2. $a = [3, 4, 2, 1]$，逆序对为：$(3, 1), (4, 1), (3, 2), (4, 2), (4, 3)$；
3. $a = [1, 2, 4, 3]$，逆序对为：$(4, 3)$；
4. $a = [1, 4, 2, 3]$，逆序对为：$(3, 2), (4, 2)$。