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

우여곡절 끝에 시작의 마을 앞까지 도착한 호반우지만 절벽 위의 마을로 향하는 계단이 마물들의 습격으로 망가져 통나무로 계단을 만들기로 하였다. 통나무를 세로로 나란히 세워 계단을 만드는데 중간중간 마물들이 위력 m의 마법을 사용해 현재까지 세운 통나무 중 가장 긴 통나무의 길이 k를 기준으로 길이가 max(k-m, 0) 이상인 통나무들의 길이를 max(k-m, 0)으로 만들어 버린다. N개의 쿼리가 주어진다. 1 a : 호반우가 길이 a의 통나무를 계단 옆에 세운다. 2 m : 마물들이 계단에 위력 m의 마법을 사용한다. 계단을 만들기에 호반우가 새로 세우는 통나무는 항상 이전에 1번 쿼리로 세운 통나무의 길이보다 길다. 계단을 보강해 주기 위해 호반우가 N개의 쿼리 이후 완성한 계단의 모든 통나무 길이의 합을 구해보자.

첫 번째 줄에 쿼리의 개수 N이 주어진다. 두 번째 줄부터 N개의 줄에 2개의 양의 정수 x, y가 공백을 두고 주어진다. x가 1이면 호반우가 길이 y의 통나무를 계단 옆에 세운 것이고 새로 세우는 통나무는 항상 이전에 1번 쿼리로 세운 통나무의 길이보다 길다. x가 2이면 마물들이 계단에 위력 y의 마법을 사용한 것이며 계단이 없는 상태에서도 2번 쿼리가 입력될 수 있다. (1 ≤ N ≤ 500,000) (1 ≤ x ≤ 2) (1 ≤ y ≤ 10^9)

N개의 쿼리 이후 완성된 통나무 계단의 모든 통나무 길이의 합을 출력한다.