구간 인버전 개수

오스타프는 의자 안에 숨겨진 다이아몬드에 이제 놀라지 않는다. 이번에도 그는 놀라지 않았다. 그의 앞에는 의자 $n$개가 놓여 있다. 의자 $i$에는 $a_i$개의 다이아몬드가 숨겨져 있으며, 모든 $a_i$는 서로 다르고 1 이상 $n$ 이하이다.

오스타프가 관심을 두는 것은 다이아몬드가 아니라 인버전의 개수다. $i < j$이고 $a_i > a_j$인 쌍 $(i, j)$를 인버전이라고 한다. 전체 의자에서 인버전을 세는 일은 그에게 쉬웠다. 이제 연속한 의자 구간마다 인버전 개수를 빠르게 세야 한다. 오스타프는 이를 해냈다. 당신은 할 수 있겠는가?

첫 줄에 의자의 개수 $n$ ($1 \le n \le 30000$)이 주어진다. 둘째 줄에는 공백으로 구분된 정수 $n$개 $a_i$ ($1 \le a_i \le n$)가 주어진다. 모든 값은 서로 다르다.

다음 줄에는 질의의 개수 $q$ ($1 \le q \le 100000$)가 주어진다. 이어서 $q$개의 줄에 질의 $i$의 경계를 만드는 데 쓰이는 두 정수 $x_i$와 $y_i$ ($1 \le x_i, y_i \le n$)가 주어진다. 경계는 $(x_i + Ans_{i-1} - 1) \bmod n + 1$과 $(y_i + Ans_{i-1} - 1) \bmod n + 1$이다. 여기서 $Ans_{i-1}$은 바로 전 질의의 답이고, $i$가 1이면 0이다. 두 값 중 작은 값이 구간의 왼쪽 끝, 큰 값이 오른쪽 끝이 된다. $a \bmod b$는 $a$를 $b$로 나눈 나머지다.

질의 $i$마다 $i$번째 줄에 $i$번째 구간의 인버전 개수를 정수 하나로 출력한다.

실제 질의의 경계는 다음과 같다.

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