水果遊戲是一種將各種水果合併，製造出體積更大的水果的遊戲。遊戲盤面可以用序列 $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 的回傳值。

請注意，範例評分器可能與實際評測使用的評分器不同。