문제
N개의 정수로 이뤄진 수열을 입력 받는다.
(1 ≤ N ≤ 50000)
다음 Q개의 질의에 대한 답을 구하여 출력한다.
(1 ≤ Q ≤ 200000)
각 질의는 수열의 임의의 연속된 구간의 최대값을 구하여 답하는 것이다.
입력
입력의 첫번째 줄에는 수열을 이루는 원소의 갯수 N(1≤N≤50,000)과
구간의 갯수 Q(1≤Q≤200,000)가 공백을 사이에 두고 입력된다.
그 다음 N개의 줄에는 순서대로 서있는 원소의 숫자가 한줄에 하나씩 입력되는데,
이는 1이상 1,000,000이하이다.
그 다음 Q개의 구간의 시작 인덱스와 끝 인덱스 A, B가 공백을 사이에 두고 입력되며,
A는 구간이 시작되는 원소의 번호, B는 구간이 끝나는 원소의 번호이며
A와 B는 1이상 N이하의 수이며 A는 B보다 작거나 같다.
출력
입력된 Q개의 구간에 대한 가장 큰 원소를 출력하는 프로그램을 작성한다.
예제1
입력
84
3
7
4
1
5
2
6
8
17
46
28
27
출력
7
5
8
7
예제2
입력
63
3
1
5
2
4
6
12
25
16
출력
3
5
6
힌트
태그
출처
comkiwer