Comparing Plants timer 4초 memory 2048MB

식물학자 헤이즐은 싱가포르 식물원의 특별한 전시회를 방문했다.

전시회에서 서로 다른 키의 n개 식물들이 원 상에 놓여있다.

이 식물들은 시계 방향으로 0부터 n - 1로 나타내고, 식물 n - 1 다음에 식물 0이 놓여있다.

각 식물 i (0 ≤ i ≤ n - 1)에 대해서, 헤이즐은 식물 i와 시계 방향으로 다음 k - 1개의 식물 각각을 비교

했고, 이 k - 1개 식물 중 식물 i보다 더 큰 식물의 개수를 나타내는 숫자 r_i를 적었다.

그래서 각 r_i는 어떤 연속적인 k개의 식물들의 상대적인 키에 따라 결정된다.

예를 들어, n = 5, k = 3, i = 3이라고 하자.

식물 i = 3로 부터 시계 방향으로 k - 1 = 2개의 식물들은 식물 4와 0이다.

만약 식물 4가 식물 3보다 크고 식물 0이 식물 3보다 작다면, 헤이즐은 r₃ = 1로 적는다.

헤이즐이 ri들을 정확히 기록했다고 가정한다.

따라서 이 숫자들과 일치하는 서로 다른 키의 식물들의 배치 형태는 적어도 하나 존재한다.

여러분은 q개 식물 쌍들의 키를 비교해 달라는 요청을 받았다.

불행히도, 여러분은 전시회에 접근하지 못한다.

여러분의 유일한 정보는 헤이즐의 노트북에 기록된 k와 수열 r₀, ... , r_n-1이다.

비교해야하는 각각의 서로 다른 두 식물 x와 y의 쌍에 대해서, 여러분은 다음 세 가지 상황 중 어떤 일이 일어났는지 결정해야 한다:

- 식물 x는 식물 y보다 확실히 크다: 배열 r과 일치하는 서로 다른 키 h₀, ... , h_n-1의 임의의 배치에 대해서, h_x > h_y을 만족한다.

- 식물 x는 식물 y보다 확실히 작다: 배열 r과 일치하는 서로 다른 키 h₀, ... , h_n-1의 임의의 배치에 대해서, h_x < h_y을 만족한다.

- 비교 불가하다: 이전 두 경우가 모두 성립하지 않는다.