大爷的字符串题

题目背景

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

题目描述

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

输入输出格式

输入格式


第一行两个数n,m,表示字符串长度与询问次数 之后一行n个数,表示字符串 由于你是大爷,所以字符集1e9 之后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 <= 100 对于另外10%的数据,n,m <= 1000 对于另外10%的数据,n,m <= 10000 对于另外10%的数据,n,m <= 100000 对于100%的数据,n,m <= 200000 保证数据向某省省选day1T2一样sb,大家尽情用暴力水过题吧! 没事,你只要在一个好学校,就算这题只能拿到10分,也可以进队了