题目描述

在 Cesenatico 有一栋高楼，共有 $N$ 层，每层住着一位居民。楼层从下往上编号为 $0$ 到 $N - 1$，居民 $r$ 住在第 $r$ 层。

每层楼都有一个阳台，居民们可以在那儿晒晒太阳，顺便种点花。他们还能顺便欣赏楼下阳台的花。由于所有的花每天都得浇水，大家决定互相帮助。每位居民都可以帮住在楼下那一层的居民浇水。

每天早上，所有居民都在时间 0 点离开大楼。起初，居民 $r$ 回家的时间是 $t_r$。如果居民 $r$ 回家的时间严格早于住在楼下的那一位，即 $t_r < t_{r - 1}$，那么居民 $r$ 就会帮居民 $r - 1$ 浇花。（否则，居民 $r - 1$ 就得自己浇花。）每天结束时，会发生以下两种事件之一：

• 类型 !：某位居民 $r$ 更新了他们回家的时间，从隔天开始生效。
• 类型 ?：某位居民 $r$ 询问他们已经帮居民 $r - 1$ 浇了多少次花。

注意：居民 $0$ 不会帮任何人浇花，而居民 $N - 1$ 的花也永远不会被别人浇。

你的任务是帮居民们回答所有 ? 类型的询问。

输入格式

第一行包含两个整数 $N$ 和 $D$，分别代表居民人数和需要追踪的天数。

下一行包含 $N$ 个整数 $t_0, t_1, \cdots, t_{N-1}$，这是每位居民最初回家的时间。

接下来有 $D$ 行，第 $i$ 行描述了第 $i$ 天结束时发生的事件。

每个事件格式如下：

• ! r x。居民 $r$ ($0 \leq r \leq N-1$) 从隔天开始在时间 $x$ 回家，也就是说 $t_r$ 的值变为 $x$。注意，$x$ 有可能和当前的 $t_r$ 相同。
• ? r。询问居民 $r$ ($1 \leq r \leq N-1$) 自第 $0$ 天开始以来，一共帮居民 $r - 1$ 浇了多少次花。

保证至少有一个 ? 事件。

输出格式

对于每个 ? 事件，输出一行一个整数：即自第 $0$ 天开始，居民 $r$ 帮居民 $r - 1$ 浇花的次数。

注意：在这个问题中，不要算上居民自己给自己浇花的次数。

3 4
7 7 5
? 2
? 1
? 2
? 2

1
0
3
4

2 5
5 7
! 1 4
? 1
! 0 4
! 1 6
? 1

1
2

4 6
13 9 15 2
! 1 18
? 3
! 0 12
! 2 1
? 1
? 2

2
1
5

3 6
5 2 4
? 1
! 1 8
! 0 10
! 1 3
? 1
? 2

1
4
2

提示

样例解释

:::align{center}

样例 1。喷壶图标表示该居民会帮楼下邻居浇花。 :::

第一个样例适用于子任务 2、4、5 和 6。由于日程从未更新，居民 $2$ 每天都比居民 $1$ 早回家，并帮他们浇花。第 $0$ 天后，居民 $2$ 帮邻居浇了一次花。由于居民 $0$ 和 $1$ 在同一时间回家，居民 $1$ 不会帮居民 $0$ 浇花。第 $1$ 天后，居民 $1$ 仍然没有帮邻居浇过花。第 $2$ 天后，居民 $2$ 帮邻居浇了三次花。第 $3$ 天后，居民 $2$ 帮邻居浇了四次花。

:::align{center}

样例 2。 :::

第二个样例适用于子任务 3、4 和 6。在第 $0$ 天，居民 $1$ 没有帮邻居浇花。第 $0$ 天后，居民 $1$ 的日程更新了。由于在第 $1$ 天他们比邻居更早回家，所以他们帮邻居浇了花。第 $1$ 天后，居民 $1$ 帮邻居浇了一次花。在第 $2$ 天，居民 $1$ 再次帮邻居浇了花。第 $4$ 天后，居民 $1$ 总共帮邻居浇了两次花。

第三个样例适用于子任务 4、5 和 6。注意此示例没有插图。

:::align{center}

样例 4。 :::

第四个样例适用于子任务 4 和 6。第 $0$ 天后，居民 $1$ 帮邻居浇了一次花。第 $4$ 天后，居民 $1$ 帮邻居浇了四次花（分别在第 $0$、第 $1$、第 $3$ 和第 $4$ 天）。居民 $2$ 总共帮邻居浇了两次花（在第 $2$ 和第 $3$ 天）。

约束条件

• $2 \leq N \leq 200\ 000$.
• $1 \leq D \leq 200\ 000$.
• $1 \leq t_r \leq 10^9$（最初以及每次变动后）。

评分方式

你的程序将在分成若干子任务的测试数据上进行测试。要获得某个子任务的分数，你必须正确解出该子任务中所有的测试数据。

• 子任务 $0$ [$0$ 分]: 样例。
• 子任务 $1$ [$9$ 分]: $D = 1$，即只有一个 ? 类型的事件。
• 子任务 $2$ [$12$ 分]: 所有事件都是 ? 类型。
• 子任务 $3$ [$13$ 分]: $N = 2$。
• 子任务 $4$ [$18$ 分]: $N \le 2000$ 且 $D \le 2000$。
• 子任务 $5$ [$21$ 分]: 每位居民最多更改一次回家时间。
• 子任务 $6$ [$27$ 分]: 没有额外的约束条件。