An array containing $n$ elements is given. Find number of distinct contiguous subsegments of length $l$, each containing at least $k$ different elements. If you sort any two segments of length $l$, and  $a_{i} = b_{i} ,\quad 1 \le i \le l$, then both the segments are considered to be same, and is counted only once. 

Input 

First line contains two space seperated integers $n$ and $q$, size of array and number of queries respectively.

Next line contains $n$ space seperated integers.

Next $q$ lines contains two space separated integers $l\quad k$,  $l$ is the size of subsegment and $k$ is the number of distinct elements in each subsegment.

Output

For each query print on a new line, the number of distinct contiguos subsegments of length $l$,  each  of which contains at least $k$ different elements.

Constraints

$1 \le n \le 10^5$

$1 \le a_i \le 10^5$

$1 \le q \le 100$

$1 \le k \le n$

$1 \le l \le 10^9$