The Fruit Game is a game where you combine various types of fruits to create a fruit of a larger type. The game board for the Fruit Game can be represented as a sequence $X[0], X[1], \dots, X[K - 1]$. Each number represents the type of fruit, where a larger number means a larger fruit size.

A player can perform a merge operation by combining two adjacent fruits of the same type to create a larger fruit. This operation is defined as follows:

Merge: On a game board represented by $X[0], X[1], \dots, X[K - 1]$, choose an integer $0 \le i \le K - 2$. If $X[i] = X[i + 1]$, the game board changes to $X[0], \dots, X[i - 1], X[i] + 1, X[i + 2], \dots, X[K - 1]$.

The player's goal is to create the largest possible fruit using zero or more merge operations, given an initial game board.

For example, if the game board is $X = [2, 1, 1, 3, 2]$, since $X[1] = X[2]$, choosing $i = 1$ and performing the merge operation changes the game board to $X = [2, 2, 3, 2]$. Since $X[0] = X[1]$, choosing $i = 0$ and performing the merge operation changes the game board to $X = [3, 3, 2]$. Finally, since $X[0] = X[1]$, choosing $i = 0$ and performing the merge operation changes the game board to $X = [4, 2]$. This way, you can create a fruit of type 4, which is the largest fruit type obtainable.

You are given a sequence $A$ of length $N$. The elements of $A$ can be changed, and these changes are cumulative. You must write a program that, given an integer pair $(l, r)$ satisfying $0 \le l \le r \le N - 1$, calculates the largest fruit type obtainable from the game board represented by $A[l], \dots, A[r]$. There are a total of $Q$ operations, where an operation is either a change to an element of the sequence or a query given by a pair $(l, r)$.

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 any other functions are called.
• If there is any preprocessing or global variable initialization required for subsequent function calls, implement it in this function.

int play_game(int l, int r)

• This function must return the largest fruit type obtainable from the game board consisting of $A[l], \dots, 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 any input/output functions in any part of your submitted source code.

Note

$A[i], \dots, A[j]$ is a sequence of length $j - i + 1$ consisting of elements from index $i$ to index $j$ of sequence $A$. For example, when $A = [3, 5, 7, 2, 9]$, $A[1], \dots, A[3]$ is $[5, 7, 2]$, and $A[4], \dots, A[4]$ is $[9]$.

Constraints

• $1 \le N, Q \le 100\,000$
• $1 \le A[i] \le 10$ for all $i$ ($0 \le i \le N - 1$)
• $0 \le l \le r \le N - 1$ for all play_game calls
• $0 \le p \le N - 1, 1 \le v \le 10$ for all update_game calls

Subtasks

1. (5 points) $N \le 10, Q \le 10$
2. (6 points) $N \le 600, Q \le 600$
3. (8 points) $N \le 4\,000, Q \le 4\,000$, $A[i] \le 2$ for all $i$, $v \le 2$ for all update_game calls
4. (15 points) $N \le 4\,000, Q \le 4\,000$
5. (12 points) $A[i] \le 2$ for all $i$, $v \le 2$ for all update_game calls
6. (14 points) update_game is not called.
7. (40 points) No additional constraints.

Examples

Examples 1

Consider the case where $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 where $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

Interaction

The sample grader receives input in the following format:

• Line 1: $N$
• Line 2: $A[0] \ A[1] \ \dots \ A[N - 1]$
• Line 3: $Q$
• Line $3 + i$ ($1 \le i \le Q$): 1 l r if play_game is called, 2 p v if update_game is called.

The sample grader outputs 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 grading.