大小为 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)。