Олимпиадный тренинг

Задача . D. Подсчет инверсий


Задача

Темы: математика Перебор *1800

Перестановкой размера 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 в противном случае.

Примечание

В первом примере:

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

Примеры
№Входные данныеВыходные данные
1 3
1 2 3
2
1 2
2 3 
odd
even
2 4
1 2 4 3
4
1 1
1 4
1 4
2 3 
odd
odd
odd
even

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет