https://www.acmicpc.net/problem/31284

# KOITST 24 Fruit Game

The fruit game is a game where various types of fruits are combined to create a larger type of fruit. The game board of the fruit game can be represented as a sequence $X[0], X[1], \cdots , X[K - 1]$. Here, each number represents the number corresponding to the type of fruit, and a higher number indicates a larger fruit.

In this game, the player can perform a merging operation that combines adjacent fruits of the same type to create a larger fruit. This merge operation is defined as follows:

If there exists an integer $0 ≤ i ≤ K - 2$ such that $X[i] = X[i + 1]$, the game board is changed to $X[0], \cdots , X[i - 1], X[i] + 1, X[i + 2], \cdots , X[K - 1]$.

The player's goal is to use the merging operation $0$ or more times to create a larger fruit given the initial game board.

For example, if the game board is $X = [2, 1, 1, 3, 2]$, we can:

1. Since $X[1] = X[2]$, select $i = 1$ and performing the merging operation results in the game board becoming $X = [2, 2, 3, 2]$.
2. Since $X[0] = X[1]$, selecting $i = 0$ and performing the merging operation results in the game board becoming $X = [3, 3, 2]$.
3. Since $X[0] = X[1]$, selecting $i = 0$ and performing the merging operation results in the game board becoming $X = [4, 2]$.

By doing so, a fruit with a number $4$ can be created, which is the largest fruit that can be obtained.

You are given a sequence $A$ of length $N$. You need to handle a total of $Q$ queries/updates of the following type:

- update $X[p]$ to $v$
- query the largest fruit that can be formed using the fruits from $A[l], \cdots , A[r]$
# Implementation

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

$A$: An integer array of size $N$.

This function is called only once and is called before any other function is called.

If there is any preprocessing or global variable setting required for subsequent function calls, it can be implemented in this function.

`int play_game(int l, int r)`

his function should return the largest fruit number that can be obtained from the game board represented by $A[l], \cdots , A[r]$.

This function is called one or more times.

`void update_game(int p, int v)`

This function should change the value of $A[p]$ to $v$.

The number of times the play_game function is called or the update_game function is called is a total of $Q$ times.

No input or output functions should be executed in any part of the submitted source code.

# Constraints

* $1 ≤ N, Q ≤ 100, 000$
* For all $i$, $1 ≤ A[i] ≤ 10$ ($0 ≤ i ≤ N - 1$)
* For all play_game calls, $0 ≤ l ≤ r ≤ N - 1$
* For all update_game calls, $0 ≤ p ≤ N - 1$, $1 ≤ v ≤ 10$

# Subtask

| ST | Score | Constraints |
| :----------------: | :------: | :---- |
| 1 | 5 | $N≤10, Q≤10$ |
| 2 | 6 | $N≤600, Q≤600$ |
| 3 | 8 |$N≤4,000, Q≤4,000$. For all $i$, $A[i] \leq 2$. For all `update_game` calls, $v \leq 2$ |
| 4 | 15 | $N≤4,000, Q≤4,000$ |
| 5 | 12 | For all $i$, $A[i] \leq 2$. For all `update_game` calls, $v \leq 2$ |
| 6 | 14 | `update_game` is not called. |
| 7 | 40 | No additional constraints. |

# Examples

### Example 1

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

The following are the functions called:

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

### Example 2

Consider $N = 7$, $A = [1, 1, 1, 1, 2, 2, 2]$

The following are the functions called:

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