题目描述

题目译自 XXVI Olimpiada Informatyczna – III etap Wyścigi

Bajtazar 又一个周六清晨沉浸在有线电视的体育频道中。今天，他将观看拜托城杯赛车大奖赛的决赛。$n$ 名车手参赛，每人已累积一定积分，但冠军将在本季最后一场比赛后揭晓。Bajtazar 屏息期待赛道上的激战。决赛积分规则为：第一名获 $n$ 分，第二名 $n-1$ 分，第三名 $n-2$ 分，以此类推，最后一名获 $1$ 分（假设无并列名次）。赛后，各车手积分加入已有积分，总积分最高者（可并列）获拜托城杯。

为增添悬念，主办方会在决赛前调整车手积分，逐步公布奖金（加分）和罚分，点燃 Bajtazar 的热情。他想知道每刻有多少车手有机会夺冠。请编写程序，处理三种查询：

• B $x$ $y$（奖金）：当前积分至少 $x$ 的车手加 $y$ 分；
• K $x$ $y$（罚分）：当前积分至多 $x$ 的车手扣 $y$ 分（积分可为负）；
• Z：查询若决赛在当前积分下举行，有多少车手可能夺冠。

你的程序需读取车手初始积分，处理奖金和罚分，回答 Bajtazar 的查询，并输出结果。

输入格式

第一行包含两个整数 $n, q$，分别表示车手数和查询数。

第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$ $(0 \leq p_i \leq 2 \cdot 10^6)$，表示车手的初始积分。

接下来的 $q$ 行，每行描述一个查询，格式为：字符 B, K 或 Z，对于 B 或 K，后接两个整数 $x, y$ $(-10^{18} \leq x \leq 10^{18}, 0 \leq y \leq 10^6)$。

保证至少有一个 Z 查询。

输出格式

对于每个 Z 查询，输出一行一个整数，表示可能夺冠的车手数。

4 3
10 8 4 8
Z
B 9 5
Z

3
1

奖金前，车手 $1$ 积分最高，若获胜必夺冠。车手 $2$ 和 $4$ 若获胜，且车手 $1$ 排名第三或第四，也可夺冠。车手 $3$ 无论如何无法夺冠。奖金后，仅车手 $1$（唯一获 $5$ 分加成）可夺冠。

附加样例

1. $n=8$，单个 Z 查询，对于 $1 \leq i \leq n$，$p_i=2i-2$。
2. $n=1000$，单个 Z 查询，$1 \leq p_i \leq n+5$，五名车手无法夺冠。
3. $n=300000, q=50000$，对于 $1 \leq i \leq n$，$p_i=n+1-i$，查询为四个元素的循环，即令循环编号 $0 \leq i < \frac{q}{4}$：
   • Z
   • K $2i$ $1$
   • Z
   • B $i+1$ $1$

数据范围与提示

所有测试点满足 $3 \leq n \leq 300000, 1 \leq q \leq 500000$。

详细子任务附加限制及分值如下表所示。