LeLe is tired of playing blocks , so he decides to go to the movies with his friends again.
When the conductor sees LeLe again , he thinks LeLe is a smart boy.If LeLe can accomplish the task given by her ,LeLe and his friends can enjoy a free film!
The task is :
All kids line up($n$ kids in total) and LeLe should find out how many pairs of kids stand in wrong position (the tall kids stands in front of the short kids.$i < j$ && $H_i > H_j$).As time goes by,some friends will join the line and some kids is so impatience that leave the line.LeLe should work out how many pairs of kids stand in wrong position when a kid leaves or joins.
However LeLe knows the relative height of all kids.The shortest is 1,and the tallest is $n$.
Input
There are multiple test cases, about $10$ cases.
The first line of input contains two integers $n,m(1 \leq n,m \leq 20000)$.
The second line contains $n$ integers $H_1,H_2,...,H_n(1 \leq H_i \leq n)$,indicate the height of each kids in the initial queue from left to right.
For the next $m$ lines ,each line means a kid leave or join.
$0$ $x$ $y$ means a kid of $y$ height stands behind the $xth$ kid,$x=0$ means stand at the front of the queue.$(1 \leq y \leq n)$
$1$ $x$ indicate the $xth$ (from left to right) kid leave.
Output
There are multiple test cases, about $10$ cases.
For each operation puts how many pairs of kids stand in wrong position.
Sample Input
5 5
5 4 3 2 1
0 0 2
0 1 3
1 3
1 3
1 3
Sample Output
11
13
9
6
4
Hint
After operator 1,the height of every kid is 2 5 4 3 2 1. The total pairs of wrong position is 11.
After operator 2,the height of every kid is 2 3 5 4 3 2 1. The total pairs of wrong position is 13.
After operator 3,the height of every kid is 2 3 4 3 2 1. The total pairs of wrong position is 9.
After operator 4,the height of every kid is 2 3 3 2 1. The total pairs of wrong position is 6.
After operator 5,the height of every kid is 2 3 2 1. The total pairs of wrong position is 4.
All operators are legal.
