D. Подсчет инверсий
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перестановкой размера n называют такой массив из n чисел, что все числа от 1 до n встречаются в нем ровно один раз. Инверсией в перестановке p называют такую пару позиций (i, j), что i > j и ai < aj. Например, перестановка [4, 1, 3, 2] содержит 4 инверсии: (2, 1), (3, 1), (4, 1), (4, 3).

Задана перестановка a размера n и 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-й из них должно быть записано odd, если количество инверсий в перестановке после i-го запроса нечетно и even в противном случае.

Примеры
Входные данные
3
1 2 3
2
1 2
2 3
Выходные данные
odd
even
Входные данные
4
1 2 4 3
4
1 1
1 4
1 4
2 3
Выходные данные
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).