大爷的字符串题

题目背景

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

题目描述

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

输入输出格式

输入格式


第一行两个数 $n$,$m$,表示字符串长度与询问次数。 之后一行 $n$ 个数,表示字符串, 由于你是大爷,所以字符集 $10^9$。 之后 $m$ 行每行两个数,表示询问的左右区间。

输出格式


$m$ 行,每行一个数表示答案。

输入输出样例

输入样例 #1

3 3
3 3 3
3 3
3 3
3 3

输出样例 #1

-1
-1
-1

说明

前 4 个点 1s,后面的点 4s。 - 对于 $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$。 保证数据像某省省选 day1T2 一样 sb,大家尽情用暴力水过题吧! 没事,你只要在一个好学校,就算这题只能拿到 10 分,也可以进队了。