水果游戏（fruitgame）

水果游戏是一个通过合并多种水果来制造更大种类水果的游戏。水果游戏的棋盘可以用序列 $X[0], X[1], \dots, X[K - 1]$ 来表示。其中每个数字代表水果种类的编号，编号越大，表示水果的体积越大。

玩家可以执行“合并”操作，将两个种类相同且相邻的水果合并成一个体积更大的水果。该操作定义如下：

合并：在由 $X[0], X[1], \dots, X[K - 1]$ 表示的棋盘上，选择一个整数 $0 \le i \le K - 2$，如果满足 $X[i] = X[i + 1]$，则将棋盘变为 $X[0], \dots, X[i - 1], X[i] + 1, X[i + 2], \dots, X[K - 1]$。

玩家的目标是在给定初始棋盘的情况下，通过执行 0 次或多次合并操作，制造出体积最大的水果。

例如，当棋盘为 $X = [2, 1, 1, 3, 2]$ 时，因为 $X[1] = X[2]$，选择 $i = 1$ 执行合并操作，棋盘变为 $X = [2, 2, 3, 2]$。接着，因为 $X[0] = X[1]$，选择 $i = 0$ 执行合并操作，棋盘变为 $X = [3, 3, 2]$。最后，因为 $X[0] = X[1]$，选择 $i = 0$ 执行合并操作，棋盘变为 $X = [4, 2]$。这样可以制造出编号为 4 的水果，这也是能得到的最大水果编号。

给定一个长度为 $N$ 的序列 $A$。$A$ 的元素可以在中间发生变化，且这些变化是累积的。你需要编写一个程序，在每次给定满足 $0 \le l \le r \le N - 1$ 的整数对 $(l, r)$ 时，求出由 $A[l], \dots, A[r]$ 表示的棋盘上能得到的最大水果编号。序列元素的变化或查询操作的总次数为 $Q$。

实现细节

你需要实现以下函数：

void prepare_game(std::vector<int> A)

• $A$: 一个大小为 $N$ 的整数数组。
• 该函数仅被调用一次，且在所有其他函数调用之前调用。
• 如果后续函数调用需要预处理或设置全局变量，可以在此函数中实现。

int play_game(int l, int r)

• 该函数应返回由 $A[l], \dots, A[r]$ 组成的棋盘上能得到的最大水果编号。
• 该函数会被调用一次或多次。

void update_game(int p, int v)

• 将 $A[p]$ 的值修改为 $v$。

play_game 函数或 update_game 函数的总调用次数为 $Q$。

提交的源代码中不得执行任何输入输出函数。

说明

$A[i], \dots, A[j]$ 是由序列 $A$ 的第 $i$ 个元素到第 $j$ 个元素组成的长度为 $j - i + 1$ 的序列。例如，当 $A = [3, 5, 7, 2, 9]$ 时，$A[1], \dots, A[3]$ 为 $[5, 7, 2]$，$A[4], \dots, A[4]$ 为 $[9]$。

数据范围

• $1 \le N, Q \le 100\,000$
• 对于所有 $i$，满足 $1 \le A[i] \le 10$ ($0 \le i \le N - 1$)
• 对于所有 play_game 调用，满足 $0 \le l \le r \le N - 1$
• 对于所有 update_game 调用，满足 $0 \le p \le N - 1, 1 \le v \le 10$

子任务

1. (5分) $N \le 10, Q \le 10$
2. (6分) $N \le 600, Q \le 600$
3. (8分) $N \le 4\,000, Q \le 4\,000$，对于所有 $i$ 满足 $A[i] \le 2$，且所有 update_game 调用满足 $v \le 2$
4. (15分) $N \le 4\,000, Q \le 4\,000$
5. (12分) 对于所有 $i$ 满足 $A[i] \le 2$，且所有 update_game 调用满足 $v \le 2$
6. (14分) 不会调用 update_game
7. (40分) 无额外限制

样例

样例 1

$N = 5, A = [2, 1, 1, 3, 4]$。 评测程序按顺序调用以下函数：

prepare_game([2, 1, 1, 3, 4])
play_game(0, 4) = 5
update_game(2, 3)
play_game(2, 4) = 5
update_game(1, 2)
play_game(0, 2) = 4

样例 2

$N = 7, A = [1, 1, 1, 1, 2, 2, 2]$。 评测程序按顺序调用以下函数：

prepare_game([1, 1, 1, 1, 2, 2, 2])
play_game(0, 6) = 4
play_game(2, 4) = 3
update_game(6, 4)
play_game(4, 6) = 4
play_game(0, 6) = 5

Sample grader

Sample grader 按以下格式接收输入：

• Line 1: $N$
• Line 2: $A[0] \ A[1] \ \dots \ A[N - 1]$
• Line 3: $Q$
• Line $3 + i$ ($1 \le i \le Q$): 若调用 play_game 函数则为 1 l r，若调用 update_game 函数则为 2 p v

Sample grader 输出以下内容：

• Line $i$: 第 $i$ 次调用的 play_game 函数返回的值

请注意，Sample grader 可能与实际评测时使用的评测程序不同。