Codeforces Round 136 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

data structures

*1800

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Little Elephant and Array

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe Little Elephant loves playing with arrays. He has array *a*, consisting of *n* positive integers, indexed from 1 to *n*. Let's denote the number with index *i* as *a*_{i}.

Additionally the Little Elephant has *m* queries to the array, each query is characterised by a pair of integers *l*_{j} and *r*_{j} (1 ≤ *l*_{j} ≤ *r*_{j} ≤ *n*). For each query *l*_{j}, *r*_{j} the Little Elephant has to count, how many numbers *x* exist, such that number *x* occurs exactly *x* times among numbers *a*_{lj}, *a*_{lj + 1}, ..., *a*_{rj}.

Help the Little Elephant to count the answers to all queries.

Input

The first line contains two space-separated integers *n* and *m* (1 ≤ *n*, *m* ≤ 10^{5}) — the size of array *a* and the number of queries to it. The next line contains *n* space-separated positive integers *a*_{1}, *a*_{2}, ..., *a*_{n} (1 ≤ *a*_{i} ≤ 10^{9}). Next *m* lines contain descriptions of queries, one per line. The *j*-th of these lines contains the description of the *j*-th query as two space-separated integers *l*_{j} and *r*_{j} (1 ≤ *l*_{j} ≤ *r*_{j} ≤ *n*).

Output

In *m* lines print *m* integers — the answers to the queries. The *j*-th line should contain the answer to the *j*-th query.

Examples

Input

7 2

3 1 2 2 3 3 7

1 7

3 4

Output

3

1

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/22/2024 12:25:56 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|