F. Permutation Subarrays
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an array $$$A$$$ of size $$$N$$$.

You have to answer $$$Q$$$ queries. Each query consists of two integers $$$l$$$ and $$$r$$$.

For each query, count the number of contiguous subarrays that satisfy both of the following conditions:

  • The length of the subarray is exactly $$$r-l+1$$$.
  • Every integer in the range $$$[l, r]$$$ appears exactly once in the subarray.

In other words, the elements of the subarray form a permutation of the integers $$$l, l+1, \ldots, r$$$.

Input

The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \le N, Q \le 2 \cdot 10^5$$$).

The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ ($$$1 \le A_i \le 2 \cdot 10^5$$$).

Each of the next $$$Q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 2 \cdot 10^5$$$).

Output

For each query, print a single integer — the number of contiguous subarrays whose length is exactly $$$r-l+1$$$ and whose elements form a permutation of all integers from $$$l$$$ to $$$r$$$.

Examples
Input
5 3
1 2 4 3 5
1 3
1 4
2 5
Output
0
1
1
Input
11 3
1 3 2 4 2 1 3 4 3 2 1
1 4
1 3
3 4
Output
4
3
2