반출 직전의 책 이웃

문제

한 도서관의 긴 서가에는 책 N권이 한 줄로 꽂혀 있다. 책에는 서로 다른 번호 1번부터 N번까지가 붙어 있으며, 처음에는 왼쪽에서 오른쪽으로 번호가 증가하는 순서로 놓여 있다. 도서관은 서가를 정리하기 위해 여러 책을 차례대로 반출하려고 한다. 반출 요청에는 책 번호 하나가 적혀 있으며, 요청은 주어진 순서대로 처리한다. 요청한 책이 현재 서가에 남아 있다면, 직원은 그 책을 꺼내기 직전에 바로 왼쪽 책과 바로 오른쪽 책의 번호를 기록한다. 여기서 이웃은 최초 배치에서의 이웃이 아니라, 앞선 요청을 모두 처리한 뒤 현재 서가에 남아 있는 책 중 바로 붙어 있는 책을 뜻한다. 기록을 마친 뒤에는 요청한 책을 서가에서 완전히 제거한다. 남은 책의 상대적인 순서는 바뀌지 않으며, 제거한 책의 양옆에 있던 책은 새로운 이웃이 된다. 요청한 책의 왼쪽에 남은 책이 없으면 왼쪽 기록에 0을 쓰고, 오른쪽에 남은 책이 없으면 오른쪽 기록에 0을 쓴다. 따라서 서가에 마지막으로 남은 책을 반출할 때의 기록은 0과 0이다. 반출한 책을 서가에 다시 꽂는 일은 없다. 같은 책의 반출 요청이 여러 번 들어올 수 있다. 요청한 책이 이미 반출되었다면 직원은 서가를 바꾸지 않고 -1과 -1을 기록한다. 책이 이미 없는 경우와 책은 있지만 이웃이 없는 경우는 서로 다른 기록을 사용한다. 모든 요청에 대해 직원이 남길 두 수를 순서대로 구한다. 요청마다 그 요청을 처리하는 시점의 상태를 사용해야 하며, 이후에 들어올 요청은 현재 기록에 영향을 주지 않는다.

입력

첫째 줄에 정수 N과 Q가 공백으로 구분되어 주어진다. 둘째 줄에 요청한 책 번호 x_1, x_2, ..., x_Q가 처리 순서대로 주어진다.
1 ≤ N ≤ 30,000
1 ≤ Q ≤ 30,000
1 ≤ x_i ≤ N
모든 수는 정수이며, 같은 책 번호가 여러 번 주어질 수 있다.

출력

Q개 줄을 출력한다. i번째 줄에는 i번째 요청의 기록을 왼쪽 번호, 오른쪽 번호 순서로 공백으로 구분하여 출력한다. 해당 방향의 이웃이 없으면 0을 사용한다. 요청한 책이 이미 반출되었다면 -1 -1을 출력한다.

5 5
3 2 3 1 5

2 4
1 4
-1 -1
0 4
4 0

1 3
1 1 1

0 0
-1 -1
-1 -1

4 4
1 4 2 3

0 2
3 0
0 3
0 0

출처: Devin.KR 자체 제작