#882. 区间最值

区间最值

题目描述

NN 个整数排成一排:A1,A2,……,ANA_1, A_2, ……, A_N

MM 次询问,每次询问给出两个整数 L,RL,R,求 AL,AL+1,……,ARA_L, A_{L+1}, ……, A_R 中最大的数是多少?

输入格式

第一行:NN。

第二行:NN 个整数 AiA_i。

第三行:MM。

接下来 MM 行:每行两个整数 L,RL, R。

输出格式

共 MM 行,每行一个数,表示对一次询问的回答。

输入样例:

6
34 1 8 123 -3 2
4
1 2
1 5
3 4
2 3

输出样例:

34
123
123
8

数据范围

对于 10% 的数据,1≤N≤104,1≤M≤1001 ≤ N ≤ 10^4, 1 ≤ M ≤ 100

对于 100% 的数据,$1 ≤ N ≤ 2×10^5, 1 ≤ M ≤ 10^5, 1 ≤ Li ≤ Ri ≤ N, |A_i| < 2^{31}$