만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

충전하기

면접 대비

시간 제한2초메모리 제한1024 MB

요약
각 연결 요청은 i 이상인 빈 포트 중 가장 작은 번호를 차지하고, 각 해제 질의는 그 포트를 채운 행동의 번호를 출력합니다.
난이도

보통10점 중 5점

유형
세그먼트 트리, 구현, 해시맵
정답자
아직 제출이 없습니다

문제

동우는 다양한 전자기기를 사용한다. 기기마다 충전기를 따로 들고 다니는 것이 번거로워서, 동우는 NN개의 포트가 있는 멀티 포트 충전기를 장만했다. 이 충전기는 특이하게도 포트마다 출력하는 전력이 다르다. ii번 포트는 ii만큼의 전력을 출력한다.

동우는 총 QQ번의 행동으로 기기를 충전기에 꽂거나 뽑는다. 행동은 두 종류이며, 다음 형식의 입력으로 주어진다.

  • 1 ii: 최소 전력이 ii인 전자기기를 ii번 포트에 꽂는다. ii번 포트에 이미 기기가 꽂혀 있다면, 비어 있는 포트 중 전력이 ii 이상이면서 가장 작은 포트에 기기를 꽂는다. 비어 있는 포트의 전력이 모두 ii 미만이라면 기기를 꽂지 않는다.
  • 2 ii: ii번 포트에 기기가 꽂혀 있다면 기기를 뽑는다.

입력

첫 번째 줄에 포트의 수 NN(1≤N≤1061 \leq N \leq 10^{6})과 행동의 수 QQ(1≤Q≤1061 \leq Q \leq 10^{6})가 주어진다. 두 번째 줄부터 QQ개의 줄에 행동의 종류 tt(t∈{1,2}t \in \{1, 2\})와 정수 ii(1≤i≤N1 \leq i \leq N)가 공백으로 구분되어 주어진다.

출력

각 행동의 결과를 한 줄에 하나씩 출력한다.

1번 행동은 기기를 꽂았다면 포트 번호를, 꽂지 않았다면 -1을 출력한다.

2번 행동은 기기가 꽂혀 있었다면 그 기기를 꽂은 행동의 번호를, 꽂혀 있지 않았다면 -1을 출력한다. 행동의 번호는 1번과 2번 행동을 합쳐서 1부터 센다.

예제2

  1. 예제 1

    입력
    2 11
1 2
1 2
1 1
2 1
2 2
1 1
1 1
1 1
2 1
1 2
1 1
    예상 출력
    2
-1
1
3
1
1
2
-1
6
-1
1

  2. 예제 2

    입력
    6 13
1 3
1 5
1 3
1 3
1 3
1 1
1 6
2 5
2 6
1 2
1 1
1 1
1 1
    예상 출력
    3
5
4
6
-1
1
-1
2
4
2
5
6
-1