← 返回题目列表

Codeforces · 911/D

D. 反转计数

中文机器翻译题面 查看原题

大小为 n 的排列是大小为 n 的数组,使得从 1 到 n 的每个整数在此数组中恰好出现一次。排列 p 中的逆是一对索引 (i, j),使得 i > j 且 ai < aj。例如,排列 [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]。

每次查询后,您必须确定反转次数是奇数还是偶数。

输入

第一行包含一个整数 n (1 ≤ n ≤ 1500) — 排列的大小。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ n) — 排列的元素。这些整数是两两不同的。

第三行包含一个整数 m (1 ≤ m ≤ 2·105) — 要处理的查询数。

接下来是 m 行,第 i 行包含两个整数 li, ri (1 ≤ li ≤ ri ≤ n) 表示第 i 个查询是反转排列的一段 [li, ri]。所有查询都是依次执行的。

输出

打印 m 行。如果第 i 个查询后的排列中的反转次数为奇数,则它们中的第 i 个必须等于奇数,否则为偶数。

示例

输入 #1

3
1 2 3
2
1 2
2 3

输出 #1

odd
even

输入 #2

4
1 2 4 3
4
1 1
1 4
1 4
2 3

输出 #2

odd
odd
odd
even

注意

第一个例子:

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)。