To earn some extra money, the cows have opened a restaurant in their barn specializing in milkshakes. The restaurant has N seats (1 <= N <= 500,000) in a row. Initially, they are all empty.
Throughout the day, there are M different events that happen in sequence at the restaurant (1 <= M <= 300,000). The two types of events that can happen are:
-
A party of size p arrives (1 <= p <= N). Bessie wants to seat the party in a contiguous block of p empty seats. If this is possible, she does so in the lowest position possible in the list of seats. If it is impossible, the party is turned away.
-
A range [a,b] is given (1 <= a <= b <= 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.
有一排n个座位，m次操作。A操作：将a名客人安置到最左的连续a个空位中，没有则不操作。L操作：[a,b]的客人离开。
求A操作的失败次数。