Description

A is the CEO of a company. Every month, employees send the company's profit data to A. A is an eccentric person who doesn't focus on whether the company is making a profit or a loss, but rather enjoys studying "perfect sequences": a continuous sequence where all numbers are distinct.

A wants to know the length of the longest perfect sequence within the interval $[L, R]$.

Input Format

The first line contains two integers $N$ and $M$, where $N$ represents $N$ consecutive months, numbered from $0$ to $N-1$, and $M$ represents the number of queries.

The second line contains $N$ integers, where the $i$-th number represents the profit value $a_i$ of the company in the $i$-th month.

The next $M$ lines each contain two integers $L$ and $R$, representing the interval queried by A.

Output Format

Output $M$ lines, each containing an integer representing the length of the longest perfect sequence within the queried interval.

Sample 1

9 2
2 5 4 1 2 3 6 2 4
0 8
2 6

6
5

Constraints and Hints

For all data, $1\le N,M\le 2\times 10^5$, $0\le L\le R\le N-1$, and $|a_i|\le 10^6$.