The *-index* is an author-level metric that measures both the productivity and citation impact of the publications of a scientist or scholar. It is defined as the maximum value of such that the given author has published papers that have each been cited at least times.

Our Mirko is nearing retirement. In his life he had published papers and now times he asks himself the following:

I wonder, what would be my -index had I only published papers through ?

Help him calculate the answers.

#### Input Specification

The first line contains integers and , the number of papers and the number of questions.

The second line contains integers , where is the number of citations of the paper.

The following lines each contain two integers and , the endpoints from the question.

#### Output Specification

Output lines. In the line output the answer to the question.

#### Constraints

Subtask | Points | Constraints |
---|---|---|

1 | 20 | |

2 | 40 | |

3 | 50 | No additional constraints. |

#### Sample Input 1

```
7 6
3 2 3 1 1 4 7
3 4
1 7
1 6
4 5
1 2
5 7
```

#### Sample Output 1

```
1
3
3
1
2
2
```

## Comments