30470번 - 호반우가 학교에 지각한 이유 3

문제

우여곡절 끝에 시작의 마을 앞까지 도착한 호반우지만 절벽 위의 마을로 향하는 계단이 마물들의 습격으로 망가져 통나무로 계단을 만들기로 하였다. 호반우는 통나무를 세로로 나란히 세워 계단을 만드는데, 중간중간 마물들이 마법을 사용해 방해하고 있다!

마물들이 위력이 $m$인 마법을 사용하면, 현재 계단을 구성하는 통나무 중 가장 긴 통나무의 길이 $k$를 기준으로 길이가 $\max (k-m,,0円)$ 이상인 통나무들의 길이를 $\max (k-m,,0円)$으로 만들어 버린다. 만약 통나무가 없다면 마법은 무시한다.

호반우와 마물들의 행동을 나타내는 $N$개의 쿼리가 다음과 같이 주어진다.

• 1 x: 호반우가 길이 $x$의 통나무를 계단 옆에 나란히 세운다.
• 2 x: 마물들이 계단에 위력 $x$의 마법을 사용한다.

호반우는 계단을 만들고 싶기에 호반우가 새로 세우는 통나무는 항상 이전에 1ドル$번 쿼리로 세운 통나무의 길이보다 길며, 마물들은 통나무가 없어도 마법을 사용할 때가 있다. 호반우가 처음으로 세우는 통나무는 따로 길이의 제한이 없다.

$N$개의 쿼리를 순서대로 전부 수행한 이후 완성된 계단을 구성하는 모든 통나무의 길이의 합을 구해보자.

입력

첫 번째 줄에 쿼리의 개수 $N$이 주어진다. $(1 \le N \le 500,000円)$

두 번째 줄부터 $N$개의 줄에 걸쳐 양의 정수 쌍 $a,,円b$가 공백을 두고 주어진다. $(a \in \{1,2\},1 \le b \le 10^{9})$

$a$가 1ドル$이면 호반우가 길이 $b$의 통나무를 계단 옆에 세운 것이고 새로 세우는 통나무는 항상 이전에 1ドル$번 쿼리로 세운 통나무의 길이보다 길다.

$a$가 2ドル$이면 마물들이 계단에 위력 $b$의 마법을 사용한 것이며 계단을 구성하는 통나무가 없는 상태에서도 2ドル$번 쿼리가 입력될 수 있다.

출력

$N$개의 쿼리를 순서대로 전부 수행한 이후 완성된 계단을 구성하는 모든 통나무의 길이의 합을 출력한다.

제한

힌트