蜀国被吴国火烧联营八百里之后，蜀国被动转为防御，但是吴和魏经常有间谍渗透到蜀国的军队中，而且间谍都成对潜伏的。

现在赵云准备进行多次查询，然后打上间谍嫌疑犯的标签；

编号只有一个或者超过两个的都不可能是间谍，现在给出m次区间l,r，请你帮赵云找出可能成为间谍的对数！

第一行三个数字n,m，表示蜀军人数和查询次数；

接下来是n个数字a_i\leq n，表示蜀军士兵类别的编号；

接下来m行，每行两个数字，表示赵云在核查l,r的区间内间谍的对数；

针对m次进行查询，输出该区间可能是成对的间谍的数量！

样例1说明：

在[1,4]之间有两个1类士兵，所以有1对；

在[2,7]之间有两个1类，两个2类，两个3类士兵，所以有3对；

[4,8]之间有个三个3类，其他都是1个，所以没有!

40%的数据：n,m \leq 3000;

100%的数据：n,m \leq 3\times 10^5;