Перестановкой размера 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
В первом примере:
Во втором примере:
