在 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, \dots, t_{N-1}$，表示每位居民最初回家的时刻。

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

每个事件为以下两种格式之一：

• ! r x：居民 $r$（$0 \le r \le N - 1$）从第二天开始在时刻 $x$ 回家，即 $t_r$ 的值变为 $x$。注意，$x$ 可能会与当前的 $t_r$ 相同。
• ? r：询问自第 $0$ 天开始以来，居民 $r$（$1 \le r \le N - 1$）已经为居民 $r - 1$ 浇了多少次花。

保证至少存在一个 ? 事件。

输出格式

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

请注意，在本题中，你不应考虑居民为自己浇花的次数。

数据范围

• $2 \le N \le 200\,000$
• $1 \le D \le 200\,000$
• 最初及每次修改后，均满足 $1 \le t_r \le 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 分）：无附加限制。

样例

输入 1

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

输出 1

1
0
3
4

输入 2

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

输出 2

1
2

输入 3

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

输出 3

2
1
5

输入 4

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

输出 4

1
4
2

说明

图 1：样例 1。浇水壶表示该居民为他们楼下的居民浇花。

第一个样例适用于子任务 2、4、5 和 6。由于时间表从未更新，居民 2 每天都比居民 1 先回家，并为居民 1 浇花。在第 0 天结束后，居民 2 为他的邻居浇了一次花。由于居民 0 和居民 1 在同一时刻回家，居民 1 不会为居民 0 浇花。在第 1 天结束后，居民 1 还没有为他的邻居浇过花。在第 2 天结束后，居民 2 为他的邻居浇了三次花。在第 3 天结束后，居民 2 为他的邻居浇了四次花。

图 2：样例 2。

第二个样例适用于子任务 3、4 和 6。在第 0 天，居民 1 没有为他的邻居浇花。在第 0 天结束后，居民 1 的时间表被更新。由于他在第 1 天比邻居回家更早，他为邻居的植物浇了水。在第 1 天结束后，居民 1 为他的邻居浇了一次花。在第 2 天，居民 1 再次为他的邻居浇花。在第 4 天结束后，居民 1 总共为他的邻居浇了两次花。

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

图 3：样例 4。

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