题目描述

给定一个长度为 $n$ 的序列 $a_{1\cdots n}$，定义 $(i,j)$（规定 $i<j$）为好点对，当且仅当满足下列条件之一：

• $i=j-1$；
• $\forall k\in(i,j),a_k\leq \min\{a_i,a_j\}$。

现在有 $m$ 组询问区间 $[l,r]$ 内好点对的个数。

给定一个 $type$，当 $type=0$ 的时候不强制在线，否则强制在线，具体操作请看输入格式。

输入格式

$1 \bmod 9$ 第一行三个整数 $n,m,type$，意义同题目描述。

第二行 $n$ 个整数 $a_{1\cdots n}$。

接下来 $m$ 行，每行两个非负整数 $l,r$。当 $type=0$，询问区间就是 $[l,r]$，否则令 $u=(l+last-1)\mod n+1,v=(r+last-1)\bmod n+1$，那么当前询问区间就是 $[\min\{u,v\},\max\{u,v\}]$，其中 $last$ 是上一次询问的答案，初始时 $last=0$。

输出格式

共 $m$ 行，第 $i$ 行一个非负整数表示第 $i$ 次询问的答案。

3 2 0
2 1 2
1 1
1 3

0
3

数据规模与约定

对于 $100\%$ 的数据，$1\leq n,m\leq 3\times 10^5$，$|a_i|\leq 10^9$。