Background

Problem Description

You are given a permutation of length $n$ and $m$ queries. Each query asks for the number of inversion pairs in a subarray interval, and the queries must be answered online.

Input Format

The first line contains two integers $n, m$.

The second line contains $n$ positive integers representing this permutation.

The next $m$ lines each contain two integers representing the query interval.

This problem is strictly online: for each query, the input numbers must be xor-ed with $lastans$. For the first query, $lastans = 0$ by default.

Output Format

Output $m$ lines. Each line contains one integer, the answer to the corresponding query.

4 1
1 4 2 3
2 4

2

Hint

$1 \le n, m \le 10^5$.

We already have an online algorithm with time complexity below $n^{1.5}$.

Source: By nzhtl1477.

Translated by ChatGPT 5