Adoption Center Satisfaction

In this problem, you are given a sequence of events occurring at a pet adoption center. The center provides two types of services:

• Receiving abandoned pets (each with a unique characteristic value).
• Adopters arriving with a desired pet characteristic value.

Every adopter has a desired pet characteristic value \(a\) (a positive integer, \(a < 2^{31}\)). Likewise, every abandoned pet is assigned a unique characteristic value. At the time an event occurs, the center processes it immediately based on the following rules:

Event Processing

• Adopter Arrival: When an adopter with desired value \(a\) arrives and there is at least one waiting pet, the adopter adopts the pet whose characteristic value is closest to \(a\). If there are two pets equally close (i.e. with characteristic values \(a-b\) and \(a+b\)), the pet with the lower characteristic value (i.e. \(a-b\)) is chosen. If no pet is waiting, the adopter is added to a waiting queue.
• Pet Arrival: When a pet with characteristic value \(p\) arrives and there is at least one waiting adopter, the pet is immediately adopted by the waiting adopter whose desired value is closest to \(p\). Again, if there is a tie (i.e. adopters with desired values \(p-b\) and \(p+b\)), the one with the lower desired value (\(p-b\)) gets the pet. If no adopter is waiting, the pet is added to a waiting list.

Once a pairing occurs, both the adopter and the pet are removed from the waiting lists. The dissatisfaction for that adoption is defined as \(|\text{pet characteristic} - \text{adopter's desired characteristic}|\). Your task is to process all the events in order and compute the total dissatisfaction of all adopters that managed to adopt a pet. Note that the system starts empty (no waiting pets and no waiting adopters).

inputFormat

The first line contains a single integer \(n\) (\(1 \leq n \leq 10^5\)) representing the number of events.

Each of the next \(n\) lines contains an event in the following format:

T a

Here, T is a character which can be either A or P. If T is A, it denotes an adopter arrival with desired pet characteristic value \(a\) (a positive integer). If T is P, it denotes a pet arrival with characteristic value \(a\) (a positive integer). It is guaranteed that all pet characteristic values are unique, and all adopter desired values are unique.

outputFormat

Output a single integer representing the total dissatisfaction, i.e. the sum of \(|\text{pet characteristic} - \text{adopter's desired characteristic}|\) for every adoption that occurs.

sample

4
A 10
P 12
P 8
A 9

3