水果游戏是一种将各种水果合并，制造出体积更大的水果的游戏。游戏盘面可以用序列 $X[0],X[1],\ldots,X[K-1]$ 表示。其中，每个数代表一种水果的编号，编号越大，表示水果体积越大。

玩家可以进行合并操作，将相邻的两个同种水果合并成更大的水果。该操作定义如下。

合并：对于盘面 $X[0],X[1],\ldots,X[K-1]$，选择一个满足 $0\le i\le K-2$ 的整数。如果 $X[i]=X[i+1]$，则将盘面变为 $X[0],\ldots,X[i-1],X[i]+1,X[i+2],\ldots,X[K-1]$。

给定初始盘面，玩家的目标是进行零次或多次合并操作，制造出体积大的水果。

例如，盘面为 $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$。序列元素可能在过程中发生改变，且这些改变会累积。每当给出满足 $0\le l\le r\le N-1$ 的整数有序对 $(l,r)$ 时，你需要求出盘面 $A[l],\ldots,A[r]$ 中能得到的最大水果编号。元素改变或给出有序对的事件共发生 $Q$ 次。

实现细节

你需要实现以下函数。

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

• $A$：大小为 $N$ 的整数数组。
• 该函数只调用一次，并且在其他所有函数调用之前调用。
• 如果后续函数调用需要预处理或全局变量初始化，可以在此函数中实现。

int play_game(int l, int r)

• 该函数需要返回在盘面 $A[l],\ldots,A[r]$ 中能得到的最大水果编号。
• 该函数至少调用一次。

void update_game(int p, int v)

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

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

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

说明

$A[i],\ldots,A[j]$ 表示由序列 $A$ 中第 $i$ 个至第 $j$ 个元素构成、长度为 $j-i+1$ 的序列。例如，当 $A=[3,5,7,2,9]$ 时，$A[1],\ldots,A[3]$ 为 $[5,7,2]$，$A[4],\ldots,A[4]$ 为 $[9]$。

数据范围

• $1\le N,Q\le100\,000$
• $1\le A[i]\le10$ ($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\le10$。

子任务

1 (5 分)

• $N\le10$.
• $Q\le10$.

2 (6 分)

• $N\le600$.
• $Q\le600$.

3 (8 分)

• $N\le4\,000$.
• $Q\le4\,000$.
• $A[i]\le2$ ($0\le i\le N-1$).
• 对于每次 update_game 调用：$v\le2$。

4 (15 分)

• $N\le4\,000$.
• $Q\le4\,000$.

5 (12 分)

• $A[i]\le2$ ($0\le i\le N-1$).
• 对于每次 update_game 调用：$v\le2$。

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

示例评分器

示例评分器按以下格式读取输入。

• 行 1: $N$.
• 行 2: $A[0]\ A[1]\ \cdots\ A[N-1]$.
• 行 3: $Q$.
• 第 $3+i$ ($1\le i\le Q$) 行：若调用 play_game，则为 1 l r；若调用 update_game，则为 2 p v。

示例评分器输出以下内容。

• 第 $i$ 行：第 $i$ 次调用 play_game 的返回值。

请注意，示例评分器可能与实际评测使用的评分器不同。