해시 테이블

이 문제에서는 해싱을 바탕으로 한 집합(set) 자료구조의 구현인 개방 주소법을 사용하는 해시 테이블을 다룬다. 해시 테이블은 해시 값을 기준으로 동작한다. 해시 값은 원소의 내용으로부터 정해진 방식으로 계산한 음이 아닌 정수이다.

해시 테이블은 0번부터 번호가 붙은 무한한 배열이다. 각 칸은 비어 있거나 원소 하나를 담고 있다. 여기서는 연산 한 가지만 고려한다. 해시 값이 $h$인 원소를 추가하는 연산이다. 이 연산은 칸 $h$, $h + 1$, $h + 2$, $\ldots$ 순서로 시도하고, 그중 처음으로 만난 빈 칸에 원소를 넣는다.

연산의 비용은 원소를 넣는 과정에서 건너뛴 점유된 칸의 개수이다. 해시 값이 5인 원소가 칸 5에 바로 들어가면 비용은 0이다. 칸 10에 들어갔다면 다섯 번 실패한 것이므로 비용은 5이다.

추가 명령의 순서를 바꾸려고 한다. 명령을 삽입하거나 삭제하고, 바뀔 때마다 이 순서대로 수행한 명령 전체의 총 비용을 구해야 한다. 각 순서를 처리하기 전에 해시 테이블은 비운다.

처음에는 명령 순서가 비어 있다. 다음 두 종류의 쿼리를 처리한다.

• + $h$ $p$: 해시 값이 $h$인 명령을 순서의 $p$번째 위치에 오도록 삽입한다.
• - $q$: $q$번째 쿼리에서 삽입한 명령을 삭제한다.

명령과 쿼리는 1번부터 번호를 매긴다. 모든 쿼리는 유효하다.

첫 줄에 쿼리의 개수 $n$이 주어진다 ($1 \leq n \leq 150\,000$). 이후 $n$개의 줄에는 각 쿼리가 한 줄씩 주어지며, 형식은 다음 두 가지 중 하나이다.

• + $h$ $p$: $0 \leq h \leq 10^5$이고 $1 \leq p \leq k + 1$이다. 여기서 $k$는 쿼리를 실행하기 전 명령 순서의 크기이다.
• - $q$: $q$번째 쿼리는 삽입 쿼리이며, 앞선 삭제 쿼리로 지워지지 않았음이 보장된다.

$n$개의 수를 한 줄에 하나씩 출력한다. $q$번째 줄에는 $q$번째 쿼리를 실행한 뒤 명령 순서에 있는 모든 명령의 총 비용을 출력한다.