시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 4 3 3 75.000%

문제

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.

서브태스크

번호 배점 조건
1 11

2 ≤ N ≤ 100

2 36

2 ≤ N ≤ 1,000

3 53

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)

채점 및 기타 정보

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