우여곡절 끝에 시작의 마을 앞까지 도착한 호반우지만 절벽 위의 마을로 향하는 계단이 마물들의 습격으로 망가져 통나무로 계단을 만들기로 하였다.

통나무를 세로로 나란히 세워 계단을 만드는데 중간중간 마물들이 위력 $m$의 마법을 사용해 현재까지 세운 통나무 중 가장 긴 통나무의 길이 $k$를 기준으로 길이가 $\max(k-m, 0)$ 이상인 통나무들의 길이를 $\max(k-m, 0)$으로 만들어 버린다.

$N$개의 쿼리가 주어진다.

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

계단을 만들기에 호반우가 새로 세우는 통나무는 항상 이전에 1번 쿼리로 세운 통나무의 길이보다 길다.

계단을 보강해 주기 위해 호반우가 $N$개의 쿼리 이후 완성한 계단의 모든 통나무 길이의 합을 구해보자.

Input

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

Output

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

Examples

Input 1

1
1 1000000000

Output 1

1000000000

Input 2

1
2 1000000000

Output 2

0