Cho dãy số A có N phần tử và Q truy vấn đếm số lượng cặp nghịch thế có trong đoạn [L .. R].

Định nghĩa cặp số (i, j) là cặp nghịch thế nếu 1 ≤ i < j ≤ N và A_i > A_j.

Input:

Dòng 1: Số nguyên N và Q (1 ≤ N, Q ≤ 3.10⁴).

Dòng 2: N số nguyên biểu diễn dãy A (1 ≤ A_i ≤ 10⁹).

Dòng 3..Q+2: Mỗi dòng chứa 2 số nguyên x, y (1 ≤ x, y ≤ N):

        Đặt u = (x - 1 + ans_last) % N + 1, v = (y - 1 + ans_last) % N + 1 (ans_last là kết quả của truy vấn liền trước, ban đầu ans_last = 0). Đoạn phần tử cần truy vấn là [min(u, v) .. max(u, v)].

Output:

Gồm Q dòng, mỗi dòng ghi kết quả của một truy vấn tương ứng.