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