背景

::::info[题目背景已折叠]

::::

题目描述

给你一个长为 $n$ 的排列，$m$ 次询问，每次查询一个区间的逆序对数，强制在线。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个正整数表示这个排列。

之后 $m$ 行，每行两个整数表示查询的区间。

本题强制在线，每次查询输入的数要 xor 上 $lastans$，第一次询问默认 $lastans=0$。

输出格式

输出m行，每行一个数表示这次询问的答案

4 1
1 4 2 3
2 4

2

提示

$1\leq n,m\leq 10^5$。

我们已经有了低于 $n^{1.5}$ 的在线算法。

Source By nzhtl1477