O jogo de frutas consiste em combinar frutas de vários tipos para criar tipos de frutas maiores. O tabuleiro pode ser representado por uma sequência $X[0],X[1],\ldots,X[K-1]$. Cada número identifica um tipo de fruta, e um identificador maior significa uma fruta maior.

O jogador pode efetuar uma operação de fusão, combinando duas frutas adjacentes do mesmo tipo numa fruta maior. A operação é definida assim.

Fusão: no tabuleiro $X[0],X[1],\ldots,X[K-1]$, escolha um inteiro $0\le i\le K-2$. Se $X[i]=X[i+1]$, substitua o tabuleiro por $X[0],\ldots,X[i-1],X[i]+1,X[i+2],\ldots,X[K-1]$.

Dado o tabuleiro inicial, o objetivo do jogador é criar uma fruta grande usando zero ou mais operações de fusão.

Por exemplo, no tabuleiro $X=[2,1,1,3,2]$, como $X[1]=X[2]$, escolher $i=1$ e fundir altera o tabuleiro para $X=[2,2,3,2]$. Como $X[0]=X[1]$, escolher $i=0$ e fundir altera-o para $X=[3,3,2]$. Finalmente, como $X[0]=X[1]$, escolher $i=0$ e fundir altera-o para $X=[4,2]$. Assim obtém-se uma fruta com identificador $4$, o maior identificador que é possível obter.

É dada uma sequência $A$ de comprimento $N$. Os seus elementos podem ser alterados e as alterações são cumulativas. Sempre que for dado um par de inteiros $(l,r)$ que satisfaça $0\le l\le r\le N-1$, encontre o maior identificador de fruta que é possível obter no tabuleiro $A[l],\ldots,A[r]$. Existem $Q$ eventos no total, cada um dos quais é uma alteração de elemento ou a apresentação de um par.

Detalhes de implementação

Deve implementar as seguintes funções.

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

• $A$: um vetor de inteiros de tamanho $N$.
• Esta função é chamada exatamente uma vez, antes de todas as outras funções.
• Qualquer pré-processamento ou inicialização de variáveis globais necessária para chamadas posteriores pode ser implementada nesta função.

int play_game(int l, int r)

• Esta função deve devolver o maior identificador de fruta que é possível obter no tabuleiro $A[l],\ldots,A[r]$.
• Esta função é chamada pelo menos uma vez.

void update_game(int p, int v)

• Altere o valor de $A[p]$ para $v$.

O número total de chamadas a play_game e update_game é $Q$.

Não deve executar funções de entrada/saída em nenhuma parte do código-fonte submetido.

Nota

$A[i],\ldots,A[j]$ é a sequência de comprimento $j-i+1$ composta pelos elementos de $i$ a $j$ de $A$. Por exemplo, quando $A=[3,5,7,2,9]$, $A[1],\ldots,A[3]$ é $[5,7,2]$, e $A[4],\ldots,A[4]$ é $[9]$.

Restrições

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

Subtarefas

1 (5 pontos)

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

2 (6 pontos)

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

3 (8 pontos)

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

4 (15 pontos)

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

5 (12 pontos)

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

6 (14 pontos)

• update_game não é chamada.

7 (40 pontos)

• Não existem restrições adicionais.

Exemplos

Exemplos 1

Considere o caso $N=5$, $A=[2,1,1,3,4]$.

O avaliador chama as seguintes funções por ordem.

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

Exemplos 2

Considere o caso $N=7$, $A=[1,1,1,1,2,2,2]$.

O avaliador chama as seguintes funções por ordem.

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

Avaliador de exemplo

O avaliador de exemplo lê a entrada no seguinte formato.

• Linha 1: $N$.
• Linha 2: $A[0]\ A[1]\ \cdots\ A[N-1]$.
• Linha 3: $Q$.
• Linha $3+i$ ($1\le i\le Q$): 1 l r para uma chamada a play_game, ou 2 p v para uma chamada a update_game.

O avaliador de exemplo imprime o seguinte.

• Linha $i$: o valor devolvido pela chamada número $i$ a play_game.

Note que o avaliador de exemplo pode ser diferente do avaliador utilizado na avaliação real.