English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
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.
[samples]
## Note
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).
大小为 #cf_span[n] 的排列是一个长度为 #cf_span[n] 的数组，其中每个从 #cf_span[1] 到 #cf_span[n] 的整数恰好出现一次。排列 #cf_span[p] 中的一个逆序对是一对下标 #cf_span[(i, j)]，满足 #cf_span[i > j] 且 #cf_span[ai < aj]。例如，排列 #cf_span[[4, 1, 3, 2]] 包含 #cf_span[4] 个逆序对：#cf_span[(2, 1)]、#cf_span[(3, 1)]、#cf_span[(4, 1)]、#cf_span[(4, 3)]。
给你一个大小为 #cf_span[n] 的排列 #cf_span[a] 和 #cf_span[m] 个对其的查询。每个查询由两个下标 #cf_span[l] 和 #cf_span[r] 表示，表示你需要将排列的区间 #cf_span[[l, r]] 反转。例如，若 #cf_span[a = [1, 2, 3, 4]] 且查询为 #cf_span[l = 2]、#cf_span[r = 4]，则得到的排列为 #cf_span[[1, 4, 3, 2]]。
每次查询后，你需要判断逆序对的数量是奇数还是偶数。
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1500]) —— 排列的大小。
第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an] (#cf_span[1 ≤ ai ≤ n]) —— 排列的元素。这些整数两两不同。
第三行包含一个整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 2·105]) —— 需要处理的查询数量。
接下来 #cf_span[m] 行，第 #cf_span[i] 行包含两个整数 #cf_span[li], #cf_span[ri] (#cf_span[1 ≤ li ≤ ri ≤ n])，表示第 #cf_span[i] 个查询是将排列的区间 #cf_span[[li, ri]] 反转。所有查询依次执行。
请输出 #cf_span[m] 行。第 #cf_span[i] 行应为 _odd_（若第 #cf_span[i] 次查询后排列的逆序对数量为奇数），否则为 _even_。
第一个例子：
第二个例子：
## Input
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1500]) —— 排列的大小。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an] (#cf_span[1 ≤ ai ≤ n]) —— 排列的元素。这些整数两两不同。第三行包含一个整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 2·105]) —— 需要处理的查询数量。接下来 #cf_span[m] 行，第 #cf_span[i] 行包含两个整数 #cf_span[li], #cf_span[ri] (#cf_span[1 ≤ li ≤ ri ≤ n])，表示第 #cf_span[i] 个查询是将排列的区间 #cf_span[[li, ri]] 反转。所有查询依次执行。
## Output
请输出 #cf_span[m] 行。第 #cf_span[i] 行应为 _odd_（若第 #cf_span[i] 次查询后排列的逆序对数量为奇数），否则为 _even_。
[samples]
## Note
第一个例子：第一次查询后 #cf_span[a = [2, 1, 3]]，逆序对：#cf_span[(2, 1)]；第二次查询后 #cf_span[a = [2, 3, 1]]，逆序对：#cf_span[(3, 1)]、#cf_span[(3, 2)]。第二个例子：#cf_span[a = [1, 2, 4, 3]]，逆序对：#cf_span[(4, 3)]；#cf_span[a = [3, 4, 2, 1]]，逆序对：#cf_span[(3, 1)]、#cf_span[(4, 1)]、#cf_span[(3, 2)]、#cf_span[(4, 2)]、#cf_span[(4, 3)]；#cf_span[a = [1, 2, 4, 3]]，逆序对：#cf_span[(4, 3)]；#cf_span[a = [1, 4, 2, 3]]，逆序对：#cf_span[(3, 2)]、#cf_span[(4, 2)]。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the size of the permutation.
Let $ A = (a_1, a_2, \dots, a_n) $ be a permutation of $ \{1, 2, \dots, n\} $.
An **inversion** is a pair $ (i, j) $ such that $ i < j $ and $ a_i > a_j $.
Let $ I(A) $ denote the total number of inversions in $ A $.
Let $ m \in \mathbb{Z}^+ $ be the number of queries.
Each query is a pair $ (l, r) $ with $ 1 \leq l \leq r \leq n $, representing the reversal of the subarray $ A[l:r] $.
**Constraints**
1. $ 1 \leq n \leq 1500 $
2. $ 1 \leq m \leq 2 \cdot 10^5 $
3. $ 1 \leq a_i \leq n $, all $ a_i $ distinct
4. $ 1 \leq l \leq r \leq n $ for each query
**Objective**
After each query, determine the parity of $ I(A) $, i.e., output **odd** if $ I(A) \mod 2 = 1 $, **even** if $ I(A) \mod 2 = 0 $.
The reversal of segment $ [l, r] $ updates $ A $, and the parity of inversions must be recomputed efficiently after each update.
API Response (JSON)
{
"problem": {
"name": "D. Inversion Counting",
"description": {
"content": "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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF911D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "大小为 #cf_span[n] 的排列是一个长度为 #cf_span[n] 的数组，其中每个从 #cf_span[1] 到 #cf_span[n] 的整数恰好出现一次。排列 #cf_span[p] 中的一个逆序对是一对下标 #cf_span[(i, j)]，满足 #cf_span[i > j] 且 #cf_span[ai < aj]。例如，排列 #cf_span[[4, 1, 3, 2]] 包含 ...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the size of the permutation. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a permutation of $ \\{1, 2, \\dots, n\\} $. \nAn **inversion** is a pair $ (i, j) $ su...",
"is_translate": false,
"language": "Formal"
}
]
}