给你一个字符串 a，每次询问一段区间的贡献。
贡献定义：每次从这个区间中拿出一个字符 x ，然后把 x 从这个区间中删除，直到区间为空。你要维护一个集合 S。

• 如果 S 为空，你 rp 减 1。
• 如果 S 中有一个元素不小于 x，则你 rp 减 1，清空 S。
• 之后将 x 插入 S。

询问搞完这段区间的字符之后最多还有多少 rp？rp 初始为 0。
询问之间不互相影响~

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

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

数据规模与约定

• 对于 10% 的数据，是样例。
• 对于另外 10% 的数据，保证 n,m≤100；
• 对于另外 10% 的数据，保证 n,m≤10³；
• 对于另外 10% 的数据，保证 n,m≤10⁴；
• 对于另外 10% 的数据，保证 n,m≤10⁵；
• 对于 100% 的数据，1≤n,m≤2×10⁵，1≤ai≤10⁹，1≤l,r≤n。

莫队 数据结构 线段树 树状数组