题目背景

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

题目描述

给你一个字符串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