정올이는 그의 늑대들에게 새로운 무리 대장을 골라 주려고 한다. 이를 위해 그는 늑대 N ( 2 \leq N \leq 10^5) 마리와 인터뷰를 진행했으며, 각각의 후보에게 리더십 능력에 기반한 능력 점수인 정수 c_i를 부여했다. 각 점수는 1에서 C 사이의 값이며, 1 \leq C \leq 10^9이다.

하지만 많은 늑대를 인터뷰했기 때문에, 정올이는 모든 늑대의 점수를 기억하지는 못하고 있다. 그러나 그는 Q ( 1 \leq Q < N) 개의 숫자 쌍 (a_j, h_j)을 기억하는데, 이는 1번 늑대부터 a_j번 늑대까지의 모든 늑대보다 더 높은 능력 점수를 가진 첫 번째 위치하는 늑대가 h_j번 늑대라는 뜻이다 (즉, 1 \leq a_j < h_j \leq N).

정올이는 노트에 능력 점수 c_1, \dots, c_N (여기서 c_i = 0이면 늑대 i의 능력 점수를 잊어버렸음을 의미)과 Q개의 쌍 (a_j, h_j)을 적어놨다. 이 정보를 바탕으로 사전순으로 가장 작은 일관된 능력 점수 열을 구하거나, 그런 열이 존재하지 않는다는 것을 밝히자 (점수 열이 사전순으로 더 작으려면, 열이 서로 다른 첫 번째 늑대의 점수가 더 작아야 한다).

#6216 upload 9 done 3 how_to_reg 3 call_split Subtask

늑대 대장 timer 2s memory 1024MB

#6216
Subtask

늑대 대장 2s 1024MB