F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Just $h$-index

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Others)
Total Submission(s): 2973    Accepted Submission(s): 1260


Problem Description
The $h$-index of an author is the largest $h$ where he has at least $h$ papers with citations not less than $h$.

Bobo has published $n$ papers with citations $a_1, a_2, \dots, a_n$ respectively.
One day, he raises $q$ questions. The $i$-th question is described by two integers $l_i$ and $r_i$, asking the $h$-index of Bobo if has *only* published papers with citations $a_{l_i}, a_{l_i + 1}, \dots, a_{r_i}$.
 

Input
The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains two integers $n$ and $q$.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$.
The $i$-th of last $q$ lines contains two integers $l_i$ and $r_i$.
 

Output
For each question, print an integer which denotes the answer.

## Constraint

* $1 \leq n, q \leq 10^5$
* $1 \leq a_i \leq n$
* $1 \leq l_i \leq r_i \leq n$
* The sum of $n$ does not exceed $250,000$.
* The sum of $q$ does not exceed $250,000$.
 

Sample Input
5 3 1 5 3 2 1 1 3 2 4 1 5 5 1 1 2 3 4 5 1 5
 

Sample Output
2 2 2 3
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-29 21:16:15, Gzip enabled