Description

Kingdom C's rival, Kingdom A, was conducting military exercises during this period.So the C Kingdom agent Mosu started working.Kingdom A has arranged n soldier camps along the coastline. The task of Mosu is to monitor the activities of these soldier camps. Because of some advanced testing methods, the number of C soldiers in each soldier camp is very clear, the number of people in each soldier camp may change, and several people may be added or reduced, but these will not escape the surveillance of Kingdom C.The CIA wants to study what tactics the enemy is doing.The CIA gave Mosu $Q$ questions. Each question has two numbers, $l$ and $r$, indicate how many types of engineering camps exist in the interval $[1,l]$and $[r, n]$. ps:Equal numbers are considered to be the same type.

Format

Input

The first line contains two numbers $N$ and $Q$, and the second line contains $n$ numbers, each of which is $a_i$, indicating that there are $a_i$ soldiers in the $i$ soldier camp.

The next $Q$ lines each contains two numbers, $l$ and $r$ for the query($1\leq n,q,a_i<=2×10^5)$

Output

Each line contains a number that is the result of the query.

Samples

3 2
1 2 1
1 2
1 3

2
1

Hint