Description

Original source: HNOI 2004

Recently, Ah Q opened a pet adoption center. The center provides two services: adopting pets abandoned by their owners and allowing new owners to adopt these pets. Each adopter hopes to adopt a pet that meets their satisfaction. Ah Q uses a special formula he invented to derive the characteristic value $a$ ($a$ is a positive integer, $a\lt 2^{31}$) that the adopter desires for the pet. He also assigns a characteristic value to each pet in the center, making it easier to manage the entire pet adoption process.

The pet adoption center always encounters two scenarios: either there are too many abandoned pets or too many adopters with too few pets:

1. When there are too many abandoned pets, if an adopter arrives hoping to adopt a pet with characteristic value $a$, they will adopt the currently unadopted pet with the characteristic value closest to $a$. No two pets will have the same characteristic value, and no two adopters will desire the same characteristic value. If there are two pets that meet the requirement, i.e., two pets with characteristic values $a-b$ and $a+b$, the adopter will adopt the pet with the characteristic value $a-b$.
2. When there are too many adopters, if a new pet arrives, which adopter can adopt it? The adopter who can adopt it is the one whose desired pet characteristic value is closest to the pet's characteristic value. If the pet's characteristic value is $a$, and there are two adopters with desired values $a-b$ and $a+b$, the adopter with the desired value $a-b$ will successfully adopt the pet. If an adopter adopts a pet with characteristic value $a$ but their desired value was $b$, their dissatisfaction level is $|a-b|$.

You are given the sequence of events over a year where adopters and pets arrive at the center. Your task is to calculate the total dissatisfaction level of all adopters who successfully adopted pets. At the beginning of the year, the center has neither pets nor adopters.

Input Format

The first line contains a positive integer $n$, representing the total number of pets and adopters arriving at the center during the year.

The next $n$ lines describe the arrivals of pets and adopters in chronological order. Each line contains two integers $a$ and $b$, where $a=0$ represents a pet, $a=1$ represents an adopter, and the positive integer $b$ represents the pet's characteristic value or the adopter's desired pet characteristic value.

At any given time, the center will only have pets or adopters, and the number of pets or adopters will not exceed $10^4$.

Output Format

Output a single positive integer, representing the total dissatisfaction level of all adopters who successfully adopted pets during the year, modulo $10^6$.

Sample 1

$|3-2|+|2-4|=3$, the last adopter has no pet to adopt.

5
0 2
0 4
1 3
1 2
1 5

3

Data Range and Hint

For all data, $1\le n\le 8\times 10^4$.