The nefarious Physicist S has constructed a death ray! Being the evil mastermind he is, he has gathered N willing volunteers to test the death ray.
The N volunteers stand in a line, each of them having life Li.
Physicist S will perform Q actions. There are two actions he can perform:
His supervisor, H, is trying to determine the number of volunteers they have to send to the hospital after the experiment (i.e. the number of volunteers who will faint during the course of the experiment). Code a program to help her!
The first line of input contains two integers, N and Q.
The next line of input contains N integers, representing the array L.
The next Q lines of input indicate Physicist S's actions. They contain a character Ci and an integer as follows:
The first and only line of output should contain a single integer, denoting the number of volunteers who faint during the experiment.
For all subtasks, 1 ≤ N, Q ≤ 100000 and 1 ≤ Li, Pi, Di ≤ 109. Ci will be either 'A' or 'B'.
Subtask 1 (30%): N, Q ≤ 1000
Subtask 2 (10%): Ci = 'A' for all updates.
Subtask 3 (20%): Physicist S fires his death ray at most 10 times.
Subtask 4 (40%): No additional constraints.
Subtask 5 (0%): Sample test cases.
5 7 1 2 3 4 5 A 1 B 3 A 2 B 2 A 2 B 3 A 1
Health after each operation is indicated below. Bold indicates the person healed on a type B operation. A person with 0 health has fainted.