Description

To earn some extra money, the cows have opened a restaurant in their barn specializing in milkshakes. The restaurant has $N$ seats in a row, numbered $1$ to $N$ ($1 \le N \le 500\,000$). Initially, all seats are empty.

Throughout the day, there are $M$ events that happen in sequence ($1 \le M \le 300\,000$). Each event is one of the following:

1. A party of size $p$ arrives ($1 \le p \le N$). Bessie wants to seat the party in a contiguous block of $p$ empty seats. If this is possible, she seats them in the block whose starting position has the smallest index. If it is impossible, the party is turned away.
2. A range $[a, b]$ is given ($1 \le a \le b \le N$), and everybody in that range of seats leaves.

Please help Bessie count the total number of parties that are turned away over the course of the day.

Input Format

• Line 1: Two space-separated integers $N$ and $M$.
• Lines $2$ to $M+1$: Each line describes a single event, either of the form "A p" (a party of size $p$ arrives) or "L a b" (all cows in the range $[a, b]$ leave).

Output Format

• Line 1: The number of parties that are turned away.

10 4 
A 6 
L 2 4 
A 5 
A 2 

1 

Hint

There are 10 seats and 4 events. First, a party of 6 cows arrives. Then all cows in seats 2..4 depart. Next, a party of 5 arrives, followed by a party of 2.

Party #3 is turned away. All other parties are seated.

Translated by ChatGPT 5