Description

Fanfan opened a pet adoption center. The center offers two services: taking in abandoned pets and allowing new owners to adopt these pets.

Each adopter hopes to adopt a satisfactory pet. Based on the adopter’s requirements, Fanfan uses a special formula of his own invention to obtain the adopter’s desired feature value $a$ ($a$ is a positive integer, $a < 2^{31}$). He also assigns a feature value to each pet in the shelter. This makes handling the entire adoption process convenient. The shelter often faces two situations: too many abandoned pets, or too many adopters and too few pets.

When there are too many abandoned pets, if an adopter arrives desiring a feature value $a$, they will adopt the currently unadopted pet whose feature value is closest to $a$. (No two pets share the same feature value, and no two adopters share the same desired feature value.) If there are two candidates with feature values $a-b$ and $a+b$, the adopter will adopt the pet with feature value $a-b$.

When there are too many adopters, if a pet arrives, which adopter can adopt it? The adopter who can adopt it is the one whose desired feature value is closest to the pet’s feature value. If the pet’s feature value is $a$ and there are two adopters desiring $a-b$ and $a+b$, then the adopter with desired value $a-b$ will successfully adopt the pet.

If an adopter adopts a pet with feature value $a$ while their desired feature value is $b$, the adopter’s dissatisfaction is $|a-b|$.

You are given the sequence of arrivals of adopters and pets at the shelter over a year. Please compute the total dissatisfaction of all adopters who successfully adopted a pet. At the beginning of the year, there are neither pets nor adopters in the shelter.

Input Format

The first line contains an integer $n$, $n \leq 80000$, the total number of pets and adopters arriving at the shelter during the year. The next $n$ lines, in order of arrival time, describe these arrivals. Each line contains two integers $a, b$, where $a \in \{0, 1\}$ ($a = 0$ indicates a pet, $a = 1$ indicates an adopter), and $b$ is the pet’s feature value or the adopter’s desired feature value. (At any given time, the shelter contains either only pets or only adopters, and their counts do not exceed $10000$.)

Output Format

Output a single integer: the total dissatisfaction of all adopters who successfully adopted a pet, modulo $1000000$.

5                  
0 2                      
0 4                         
1 3
1 2
1 5

3

Hint

Sample explanation:

Note: $|3-2| + |2-4| = 3$. The last adopter has no pet to adopt.

Translated by ChatGPT 5