Migrated from Lutece 1157 数列(seq)

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给出一个长度为n的数列A。现有如下两种操作：

修改操作：把数列中第i个数改为x

询问操作：给定一个位置i，问数列中有多少个位置j ( j>i )，满足位置i与位置j间所有的数都不超过Ai与Aj的较大值。

现共有m个操作，请对每个询问操作做出回答。

Input

第一行两个正整数n、m。

随后n行，每行一个正整数Ai。

随后m行，若是修改操作，则以一个大写C开头，随后两个正整数i和x；若是查询操作，则以一个大写Q开头，随后一个正整数i。

Output

每行一个整数，依次对每个询问操作给出回答。

Samples

5 3
1
3
2
3
2
Q 1
C 1 3
Q 1

2
4

Note

对于40%的数据，n、m<=5000

对于100%的数据，n、m<=50000，|Ai|、x<=100000