AT_awc0005_e 山の高さ調査

Takahashi works as a mountain guide and manages information about $ N $ mountains in a mountain range. The mountains are numbered from $ 1 $ to $ N $ , and the elevation of the $ i $ -th mountain is $ A_i $ meters ( $ 1 \leq i \leq N $ ). Takahashi has received $ Q $ queries from tourists. The $ j $ -th query ( $ 1 \leq j \leq Q $ ) specifies the mountains from the $ L_j $ -th to the $ R_j $ -th, and asks for the highest elevation among them. For each query, find the maximum elevation among the mountains in the specified range.

> $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_Q $ $ R_Q $ - The first line contains an integer $ N $ representing the number of mountains and an integer $ Q $ representing the number of queries, separated by a space. - The second line contains integers $ A_1, A_2, \ldots, A_N $ representing the elevations of each mountain, separated by spaces. - $ A_i $ represents the elevation (in meters) of the $ i $ -th mountain. - In the following $ Q $ lines, the $ j $ -th line ( $ 1 \leq j \leq Q $ , which is the $ (2 + j) $ -th line of the entire input) contains the left endpoint $ L_j $ and the right endpoint $ R_j $ of the range specified by the $ j $ -th query, separated by a space.

Output $ Q $ lines. The $ j $ -th line ( $ 1 \leq j \leq Q $ ) should contain the answer to the $ j $ -th query, that is, the maximum elevation among the mountains from the $ L_j $ -th to the $ R_j $ -th.

### Constraints - $ 1 \leq N \leq 10^5 $ - $ 1 \leq Q \leq 10^5 $ - $ 1 \leq A_i \leq 10^9 $ $ (1 \leq i \leq N) $ - $ 1 \leq L_j \leq R_j \leq N $ $ (1 \leq j \leq Q) $ - All inputs are integers