Fruit Game is a game in which fruits of various types are combined to create larger types of fruit. The board can be represented by a sequence $X[0],X[1],\ldots,X[K-1]$. Each number is the identifier of a fruit type, and a larger identifier means a larger fruit.

The player may perform a merge operation, combining two adjacent fruits of the same type into a larger fruit. The operation is defined as follows.

Merge: on the board $X[0],X[1],\ldots,X[K-1]$, choose an integer $0\le i\le K-2$. If $X[i]=X[i+1]$, replace the board with $X[0],\ldots,X[i-1],X[i]+1,X[i+2],\ldots,X[K-1]$.

Given the initial board, the player’s goal is to create a large fruit using zero or more merge operations.

For example, on the board $X=[2,1,1,3,2]$, since $X[1]=X[2]$, choosing $i=1$ and merging changes the board to $X=[2,2,3,2]$. Since $X[0]=X[1]$, choosing $i=0$ and merging then changes it to $X=[3,3,2]$. Finally, since $X[0]=X[1]$, choosing $i=0$ and merging changes it to $X=[4,2]$. This creates a fruit with identifier $4$, which is the largest fruit identifier obtainable.

You are given a sequence $A$ of length $N$. Its elements may change, and these changes are cumulative. Whenever an integer pair $(l,r)$ satisfying $0\le l\le r\le N-1$ is given, you must find the largest fruit identifier obtainable on the board $A[l],\ldots,A[r]$. There are $Q$ events in total, each being an element change or the presentation of a pair.

Implementation Details

You must implement the following functions.

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

• $A$: an integer array of size $N$.
• This function is called exactly once, before all other functions.
• Any preprocessing or global variable initialization needed for later calls may be implemented in this function.

int play_game(int l, int r)

• This function must return the largest fruit identifier obtainable on the board $A[l],\ldots,A[r]$.
• This function is called at least once.

void update_game(int p, int v)

• Change the value of $A[p]$ to $v$.

The total number of calls to play_game and update_game is $Q$.

You must not execute input/output functions anywhere in your submitted source code.

Note

$A[i],\ldots,A[j]$ is the sequence of length $j-i+1$ consisting of elements $i$ through $j$ of $A$. For example, when $A=[3,5,7,2,9]$, $A[1],\ldots,A[3]$ is $[5,7,2]$, and $A[4],\ldots,A[4]$ is $[9]$.

Constraints

• $1\le N,Q\le100\,000$
• $1\le A[i]\le10$ ($0\le i\le N-1$).
• For every call to play_game: $0\le l\le r\le N-1$.
• For every call to update_game: $0\le p\le N-1$, $1\le v\le10$.

Subtasks

1 (5 points)

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

2 (6 points)

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

3 (8 points)

• $N\le4\,000$.
• $Q\le4\,000$.
• $A[i]\le2$ ($0\le i\le N-1$).
• For every call to update_game: $v\le2$.

4 (15 points)

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

5 (12 points)

• $A[i]\le2$ ($0\le i\le N-1$).
• For every call to update_game: $v\le2$.

6 (14 points)

• update_game is not called.

7 (40 points)

• No additional constraints.

Examples

Examples 1

Consider the case $N=5$, $A=[2,1,1,3,4]$.

The grader calls the following functions in order.

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

Examples 2

Consider the case $N=7$, $A=[1,1,1,1,2,2,2]$.

The grader calls the following functions in order.

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

The sample grader reads input in the following format.

• Line 1: $N$.
• Line 2: $A[0]\ A[1]\ \cdots\ A[N-1]$.
• Line 3: $Q$.
• Line $3+i$ ($1\le i\le Q$): 1 l r for a call to play_game, or 2 p v for a call to update_game.

The sample grader prints the following.

• Line $i$: the value returned by the $i$-th call to play_game.

Note that the sample grader may differ from the grader used in actual judging.