【题目描述】

Mirko是一个非常单纯的人，他的好朋友给他一个有N个自然数的数组，然后对他进行Q次查询.

每一次查询包含两个正整数L,R，表示一个数组中的一个区间[L,R]，Mirko需要回答在这个区间中有多少个值刚好出现2次。

【输入】

第一行包含两个整数N和Q(1<=N,Q<=500000)

第二行包含N个自然数，这些数均小于1000000000，表示数组中的元素。

接下来有Q行，每行包含两个整数L和R(1<=L<=R<=N)。

【输出】

输出包含Q行，每行包含一次查询的答案。

样例输入1

5 1

1 2 1 1 1

1 3

样例输出1

1

样例输入2

5 2

1 1 1 1 1

2 4

2 3

样例输出2

0

1

样例输入3

5 2

1 1 2 2 3

1 1

1 5

样例输出3

0

2