El juego de frutas consiste en combinar frutas de distintos tipos para crear tipos de frutas más grandes. El tablero se puede representar mediante una secuencia $X[0],X[1],\ldots,X[K-1]$. Cada número identifica un tipo de fruta, y un identificador mayor significa una fruta más grande.

El jugador puede realizar una operación de fusión, combinando dos frutas adyacentes del mismo tipo en una fruta más grande. La operación se define así.

Fusión: en el tablero $X[0],X[1],\ldots,X[K-1]$, elige un entero $0\le i\le K-2$. Si $X[i]=X[i+1]$, sustituye el tablero por $X[0],\ldots,X[i-1],X[i]+1,X[i+2],\ldots,X[K-1]$.

Dado el tablero inicial, el objetivo del jugador es crear una fruta grande utilizando cero o más operaciones de fusión.

Por ejemplo, en el tablero $X=[2,1,1,3,2]$, como $X[1]=X[2]$, elegir $i=1$ y fusionar cambia el tablero a $X=[2,2,3,2]$. Como $X[0]=X[1]$, elegir $i=0$ y fusionar lo cambia a $X=[3,3,2]$. Por último, como $X[0]=X[1]$, elegir $i=0$ y fusionar lo cambia a $X=[4,2]$. Así se crea una fruta con identificador $4$, que es el mayor identificador que se puede obtener.

Se da una secuencia $A$ de longitud $N$. Sus elementos pueden cambiar y los cambios son acumulativos. Cada vez que se dé un par de enteros $(l,r)$ que cumpla $0\le l\le r\le N-1$, debes encontrar el mayor identificador de fruta que se pueda obtener en el tablero $A[l],\ldots,A[r]$. Hay $Q$ eventos en total, cada uno de los cuales es un cambio de elemento o la presentación de un par.

Detalles de implementación

Debes implementar las siguientes funciones.

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

• $A$: un arreglo de enteros de tamaño $N$.
• Esta función se llama exactamente una vez, antes que todas las demás funciones.
• En esta función puedes implementar cualquier preprocesamiento o inicialización de variables globales necesario para las llamadas posteriores.

int play_game(int l, int r)

• Esta función debe devolver el mayor identificador de fruta que se pueda obtener en el tablero $A[l],\ldots,A[r]$.
• Esta función se llama al menos una vez.

void update_game(int p, int v)

• Cambia el valor de $A[p]$ a $v$.

El número total de llamadas a play_game y update_game es $Q$.

No debes ejecutar funciones de entrada/salida en ninguna parte del código fuente enviado.

Nota

$A[i],\ldots,A[j]$ es la secuencia de longitud $j-i+1$ compuesta por los elementos desde $i$ hasta $j$ de $A$. Por ejemplo, cuando $A=[3,5,7,2,9]$, $A[1],\ldots,A[3]$ es $[5,7,2]$ y $A[4],\ldots,A[4]$ es $[9]$.

Restricciones

• $1\le N,Q\le100\,000$
• $1\le A[i]\le10$ ($0\le i\le N-1$).
• Para cada llamada a play_game: $0\le l\le r\le N-1$.
• Para cada llamada a update_game: $0\le p\le N-1$, $1\le v\le10$.

Subtareas

1 (5 puntos)

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

2 (6 puntos)

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

3 (8 puntos)

• $N\le4\,000$.
• $Q\le4\,000$.
• $A[i]\le2$ ($0\le i\le N-1$).
• Para cada llamada a update_game: $v\le2$.

4 (15 puntos)

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

5 (12 puntos)

• $A[i]\le2$ ($0\le i\le N-1$).
• Para cada llamada a update_game: $v\le2$.

6 (14 puntos)

• No se llama a update_game.

7 (40 puntos)

• No hay restricciones adicionales.

Ejemplos

Ejemplos 1

Considera el caso $N=5$, $A=[2,1,1,3,4]$.

El evaluador llama a las siguientes funciones en orden.

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

Ejemplos 2

Considera el caso $N=7$, $A=[1,1,1,1,2,2,2]$.

El evaluador llama a las siguientes funciones en orden.

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

Evaluador de ejemplo

El evaluador de ejemplo lee la entrada con el siguiente formato.

• Línea 1: $N$.
• Línea 2: $A[0]\ A[1]\ \cdots\ A[N-1]$.
• Línea 3: $Q$.
• Línea $3+i$ ($1\le i\le Q$): 1 l r para una llamada a play_game, o 2 p v para una llamada a update_game.

El evaluador de ejemplo imprime lo siguiente.

• Línea $i$: el valor devuelto por la llamada número $i$ a play_game.

Ten en cuenta que el evaluador de ejemplo puede ser distinto del utilizado en la evaluación real.