Informatica Online Judge

  나무꾼 민제 [2399 / 095F]

Time Limit(Test case) : 1500(ms)
Number of users who solved : 9   Total Tried : 9


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

[35th 이강민]
Writer ID : [gs17074]

Background

민제가 사는 숲에는 N개의 나무가 있고, 나무는 1번부터 N번까지 번호를 매길 수 있다.

그리고 민제는 나무들을 쉽게 분류하기 위해 각 나무의 종류를 1부터 N사이의 수로 표현할 것이다.

그런데 민제는 NYPC에서 상금을 받지 못해서 보수가 큰 나무들만 벨 것이다.

현재 나무 시장에서는 "대중적인 나무"를 팔아야 많은 보수를 받을 수 있다.

현재 시장에서는 l번 나무부터 r번 나무 중 같은 종류의 나무가 (r - l + 1) / k개 초과 있다면 그 나무 종류를 "대중적인 나무"라고 한다. (2 <= k <= 5)

하지만 시장에서 대중적인 나무는 매일 바뀌기 때문에, 각 날마다 민제에게 대중적인 나무가 무엇인지 알려주어야 하고, 없다면 없다고 알려주어야 한다.

대중적인 나무 종류가 여러개라면, 그 대중적인 나무들 중 가장 작은 번호를 알려주어야 한다.

이렇게 민제에게 알려주면 민제는 기분좋게 나무를 베고 보수를 받으며, 그 나무는 다음 날 바로 다시 자란다.

예를 들어, 1, 2번 나무의 종류가 1이고 3, 4번 나무의 종류가 2라고 하자.

l = 1, r = 3, k = 2 라면 1번 나무부터 3번 나무를 봤을 때 종류 1의 나무가 2개, 종류 2의 나무가 1개인데, 종류 1의 나무가 (3 - 1 + 1) / 2 개 초과 있으므로 대중적인 나무는 1이다.

만약 대중적인 나무가 없다면 -1이라고 알려주어야 한다.

Input

N Q
a_1 ... a_N
l_1 r_1 k_1
...
l_Q r_Q k_Q

첫째 줄에 나무의 개수 N과 민제를 도와주어야 하는 날의 수 Q가 주어진다.
둘째 줄에 i번째 나무의 종류인 a_i가 주어진다.
3 ~ Q + 2번째 줄까지 각 날마다 시장에서 제시하는 l, r, k의 값이 주어진다.

1 <= N, Q <= 300,000

Output

각 날마다 대중적인 나무 중 최솟값이 무엇인지, 없다면 -1을 줄을 나누어 출력하라.

IO Example

입력1
4 2
1 1 2 2
1 3 2
1 4 2

출력1
1
-1

입력2
5 3
1 2 1 3 2
2 5 3
1 2 3
5 5 2

출력2
2
1
2

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