Informatica Online Judge

  범인을 잡아라. [0766 / 02FE]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 133   Total Tried : 173


The Champion of this Problem (C++) : gs16042 - ms / 343byte
My Best Submission (C++) : N/A

[JKJeong 2014]

Background

GSHS에 도둑이 들었다.

GSHS의 경곽이는 도둑이 음주 후 도주했다는 사실을 알아내었다.
이번에 경곽이는 R&E를 통하여 원거리 음주 측정기를 개발했다. 이 음주 측정기는 측정자로 부터 떨어져서 여러 명을 동시에 측정할 수 있는 기기이다.

편의상 1부터 N까지 번호가 부여된 N명의 용의자들이 줄을 서 있고, a에서 b구간(단, a<=b)의 모든 사람들을 음주 측정하고자 한다.

경곽이가 K번을 측정할 때, 각 측정 시에 범인일 확률이 가장 높은 사람(수치가 가장 높은 사람)의 측정치를 출력하는 프로그램을 작성하시오.

Input

첫 번째 줄에 용의자의 수 N이 입력된다. (단, N은 1,000,000이하의 자연수)
두 번째 줄에 검사할 횟수 K가 입력된다. (단, K는 1,000이하의 자연수)
다음 줄에 N개의 측정값이 공백으로 구분되어 입력된다
다음 줄부터 K줄에 걸쳐서 구간의 범위 a, b가 공백으로 구분되어 입력된다.
(단, 1<=a<=b<=1,000,000)

Output

각 구간별로 가장 높은 수치를 한 줄에 하나씩 K줄 출력한다.

IO Example

입력
5
3
10 3 2 4 5
1 2
2 3
1 5

출력
10
3
10

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]