29241번 - Инверсии 다국어

문제

Остапа уже не удивишь бриллиантами в стульях. Вот и сейчас он не удивлен: перед ним стоят $n$ стульев. Остап знает, что в $i$ стуле спрятано $a_i$ бриллиантов, причем все $a_i$ различны и лежат в отрезке от 1 до $n$.

Но Остапа интересуют не сами бриллианты, а нечто совершенно иное. Он заинтересован в количестве инверсий. Инверсией называется такая пара $(i, j),ドル что $i < j$ и $a_i > a_j$. Считать количество инверсий среди всех стульев Остап научился легко. Теперь перед ним стоит более сложная задача: научиться быстро и без заминки считать количество инверсий среди некоторого количества подряд стоящих стульев. Остап справился, а сможете ли Вы?

입력

В первой строке находится целое число $n$ (1ドル \le n \le 30{,円}000$) --- количество стульев. Во второй строке находятся $n$ целых чисел $a_i$ (1ドル \le a_i \le n$), разделенных пробелами. Гарантируется, что все эти числа различны.

В следующей строке находится целое число $q$ (1ドル \le q \le 100{,円}000)$ --- число запросов. Следующие $q$ строк содержат по два числа $x_i$ и $y_i$ (1ドル \le x_i, y_i \le n$), необходимые для генерации границ $i$ запроса. Сами границы определяются как $(x_i + Ans_{i-1} - 1) \mod n + 1$ и $(y_i + Ans_{i-1} - 1) \mod n + 1,ドル где $Ans_{i-1}$ --- ответ на предыдущий запрос, либо 0, если $i$ равно 1. Минимальное из этих двух чисел будет левой границей отрезка, а максимальное --- правой. $a\mod b$ равно остатку от деления $a$ на $b$.

출력

Для запроса $i$ выведите в строке с номером $i$ единственное число: количество инверсий на $i$-м отрезке.

제한

노트

Истинные границы запросов выглядят следующим образом:

1. 1 5
2. 3 8
3. 2 4
4. 2 7
5. 6 8
6. 1 8