U472972 小 Y 之序列

给定一个长度为 $n$ 的序列 $a$，再给定 $m$ 个询问。 每个询问给定一个区间 $[l,r]$，求有多少个 $a_i$ 满足存在 $a_j,a_k>a_i \wedge l \le j

第一行两个整数 $n,m$。 第二行 $n$ 个整数，表示序列 $a$。 接下来的 $m$ 行，每行两个整数 $l,r$，表示加密后的询问区间。 - 解密方法：设 $lastans$ 为上一个答案，则真正的 $l$ 为 $(l \oplus lastans) \mod n+1$，$r$ 同理。若 $l>r$，则交换 $l,r$。

每行一个整数，表示答案，共 $m$ 行。

$1 \le n,m \le 3 \times 10^5$ $0 \le |a_i| \le 10^9$