H-Index Queries

The \(H\)-index measures a researcher's impact based on their number of papers and the citations they have received. A scholar's \(H\)-index is defined as the largest integer \(h\) such that the researcher has at least \(h\) papers with at least \(h\) citations each.

Mirko has published \(n\) papers. He has \(q\) queries. In each query, he wonders: if he only considered the papers from index \(l_i\) to \(r_i\) (1-indexed), what would his \(H\)-index be?

inputFormat

The first line contains two integers \(n\) and \(q\).

The second line contains \(n\) integers, where the \(i\)-th integer represents the number of citations for the \(i\)-th paper.

Then \(q\) lines follow, each containing two integers \(l_i\) and \(r_i\) (1-indexed) representing the range of papers to be considered.

outputFormat

For each query, output a single integer on a new line — the \(H\)-index computed for the subarray of papers from \(l_i\) to \(r_i\).

sample

5 3
4 3 0 1 5
1 3
2 4
1 5

2
1
3