Description

二次元的由乃为了致富，决定引进日本的椰子树。由乃的椰子园十分现代化，椰子园中有一套独特的交通系统。但

是日本没有椰子树啊。。。所以这一切都是由乃的梦。由乃梦到自己的椰子树上涨了好多好多椰子，非常高兴--直

到她看到了一个数据结构题：给你一个字符串a，每次询问一段区间的贡献

贡献定义：

每次从这个区间中随机拿出一个字符x，然后把x从这个区间中删除，你要维护一个集合S如果S为空，你rp减1如果S

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

由于由乃不是大爷，平时做过的题考试都不会考到，所以每次询问你搞完这段区间的字符之后最多还有多少rp？rp

初始为0询问之间不互相影响~由于由乃最近没事干，所以她决定卡常卡空间，请注意

Format

Input

第一行两个数n，m，表示字符串长度与询问次数

之后一行n个数，表示字符串

由于你是大爷，所以字符集1e9

之后m行每行两个数，表示询问的左右区间

Output

m行，每行一个数表示答案

Samples

3 3
3 3 3
3 3
3 3
3 3

-1
-1
-1