题目描述

给一个长为 n 的序列 A1,A2,...,An,定义(i,j)(规定i<j)为好点对,当且仅当满足下列条件之一:

  • i = j - 1
  • $\forall k\in (i,j),A_k < min(A_i,A_j)$

现在有 m 组询问,每组询问给定一个区间,求这个区间内的好点对的个数。

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

输入格式

输入第一行三个正整数 n,m,Type,分别表示序列长度,询问的个数,输入数据的种类。

输入第二行,共 n 个正整数。第 i 个数表示 Ai。

接下来 m 行,每行两个非负整数 l,r。当 Type = 0 的时候,询问区间就是 [l,r],否则令:

u = (l + last - 1) mod n + 1 , v = (r + last - 1) mod 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

数据范围及约定

测试点 n m Type Ai 特殊性质
1 <= 100 <= 100 = 0 <= 100
2 <= 1000 = 1 = 0 <= 1000
3 <= 1000 <= 1000 = 0 <= 1000 所有Ai都相等
4 <= 1000 <= 1000 = 0 <= 1000
5,6,7 <= 105 <= 105 = 0 <= 109
8,9,10 <= 3*105 <= 3*105 = 1 <= 109