시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB138866.667%

## 문제

Xylophone is a musical instrument which is played by striking wooden bars. A single wooden bar will always sound the same pitch, so a xylophone consists of bars with various pitches.

JOI-kun bought a xylophone consisting of N wooden bars. The bars are lined up in a row and numbered 1 through N from left to right. The bar with number i (1 ≤ i ≤ N) sounds a pitch of height Ai (1 ≤ Ai ≤ N). Different bars sound different pitches. He knows that the bar with the lowest pitch has a smaller number than the bar with the highest pitch.

Because JOI-kun does not know which bar sounds which pitch, he is going to study the pitch of the bars.

JOI-kun has a peculiar sense of sound; when he hears multiple sounds simultaneously, he can tell the difference between the heights of the highest pitch and the lowest pitch. He can strike a lump of bars at a time and hear their sounds. That is, for integers s and t (1 ≤ s ≤ t ≤ N), he can strike the bars with numbers s through t simultaneously, to know the difference between the maximum and the minimum among As, As+1, . . . , At.

He wants determine the pitches of the bars within 10 000 tries of striking.

## 구현

You should implement the following function solve to find the pitches of the bars.

• solve(N)
• N: the number of bars.
• This function is called exactly once for a test case.

Your program can call the following function prepared by the grader.

• query(s, t)
• This function returns the difference between the maximum and the minimum among the sounds of bars in the specified interval.
• s, t: s is the first number and t is the last number in the interval of bars to strike. That is, you strike all the bars with number at least s and at most t.
• It must hold that 1 ≤ s ≤ t ≤ N.
• You cannot call query more than 10 000 times.
• If some of the above conditions are not satisfied, your program will be judged Wrong Answer.
• answer(i, a)
• Your program should answer the pitches of the bars using this function.
• i, a: these mean that you answer Ai is a, where Ai is the height of the pitch of bar i.
• It must hold that 1 ≤ i ≤ N.
• You cannot call this function for the same value of i more than once.
• You must call this function exactly N times before the function solve terminates.
• If some of the above conditions are not satisfied, your program will be judged Wrong Answer.
• If some of the pitches you answered are different from the actual ones, your program will be judged Wrong Answer.

## 예제

An example of communication for N = 5, [A1, A2, A3, A4, A5] = [2, 1, 5, 4, 3] is shown below.

Call Return
query(1, 5)
4
answer(1, 2)
query(3, 5)
2
answer(2, 1)
answer(3, 5)
answer(5, 4)
answer(4, 3)

## 제한

• 1 ≤ Ai ≤ N (1 ≤ i ≤ N)
• Ai ≠ Aj (1 ≤ i < j ≤ N)
• For i and j with Ai = 1 and Aj = N, it holds that i < j.

번호배점제한
111

2 ≤ N ≤ 100

236

2 ≤ N ≤ 1,000

353

2 ≤ N ≤ 5,000

## 샘플 그레이더

The sample grader reads the input in the following format:

• line 1: N
• line 1 + i (1 ≤ i ≤ N): Ai

If your program answer the pitches correctly when solve terminates, the sample grader prints Accepted : Q with Q being the number of calls to query.

If your program is judged Wrong Answer, it prints Wrong Answer.

## 제출할 수 있는 언어

C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)

## 채점 및 기타 정보

• 예제는 채점하지 않는다.