大爷的字符串题

在那遥远的西南有一所学校， /\*被和谐部分\*/ 然后去参加该省省选虐场， 然后某蒟蒻不会做，所以也出了一个字符串题：

给你一个字符串 $a$，每次询问一段区间的贡献。 贡献定义： 每次从这个区间中拿出一个字符 $x$ ，然后把 $x$ 从这个区间中删除，直到区间为空。你要维护一个集合 $S$。 - 如果 $S$ 为空，你 rp 减 $1$。 - 如果 $S$ 中有一个元素不小于 $x$，则你 rp 减 $1$，清空 $S$。 - 之后将 $x$ 插入 $S$。 由于你是大爷，平时做过的题考试都会考到，所以每次询问你搞完这段区间的字符之后最多还有多少 rp？rp 初始为 $0$。 询问之间不互相影响~

第一行两个整数 $n$，$m$，表示字符串长度与询问次数。 之后一行 $n$ 个数，第 $i$ 个整数表示给出的字符串的第 $i$ 个字符 $x_i$。 接下来 $m$ 行，每行两个整数 $l, r$，表示一次询问的区间。

对于每次询问，输出一行一个整数表示答案。

3 3
3 3 3
3 3
3 3
3 3

-1
-1
-1

#### 数据规模与约定 - 对于 $10\%$ 的数据，是样例。 - 对于另外 $10\%$ 的数据，保证 $n,m \le 100$； - 对于另外 $10\%$ 的数据，保证 $n,m \le 10^3$； - 对于另外 $10\%$ 的数据，保证 $n,m \le 10^4$； - 对于另外 $10\%$ 的数据，保证 $n,m \le 10^5$； - 对于 $100\%$ 的数据，$1 \leq n,m \le 2 \times10^5$，$1 \leq a_i \leq 10^9$，$1 \leq l, r \leq n$。 保证数据像某省省选 day1T2 一样 sb，大家尽情用暴力水过题吧！ 没事，你只要在一个好学校，就算这题只能拿到 10 分，也可以进队了。