フルーツゲームは、さまざまな種類の果物を合体させて、より大きな種類の果物を作るゲームです。盤面は数列 $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]$ に変更します。

初期盤面が与えられたとき、プレイヤーの目標は、合体操作を 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$ が与えられます。その要素は途中で変更されることがあり、変更は累積します。$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$ の整数配列。
• この関数はちょうど 1 回、ほかのすべての関数より先に呼び出されます。
• 後の関数呼び出しに必要な前処理や大域変数の初期化があれば、この関数内に実装できます。

int play_game(int l, int r)

• この関数は盤面 $A[l],\ldots,A[r]$ から得られる最大の果物の番号を返す必要があります。
• この関数は少なくとも 1 回呼び出されます。

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 呼び出しの返り値。

サンプルグレーダは、実際の採点に使われるグレーダと異なる可能性があることに注意してください。