Das Früchtespiel ist ein Spiel, bei dem Früchte verschiedener Arten zusammengeführt werden, um größere Fruchtarten zu erzeugen. Das Spielfeld lässt sich als Folge $X[0],X[1],\ldots,X[K-1]$ darstellen. Jede Zahl ist die Kennnummer einer Fruchtart, wobei eine größere Kennnummer eine größere Frucht bedeutet.

Der Spieler darf zwei benachbarte Früchte derselben Art durch eine Verschmelzungsoperation zu einer größeren Frucht verbinden. Die Operation ist wie folgt definiert.

Verschmelzen: Wähle auf dem Spielfeld $X[0],X[1],\ldots,X[K-1]$ eine ganze Zahl $0\le i\le K-2$. Falls $X[i]=X[i+1]$, ersetze das Spielfeld durch $X[0],\ldots,X[i-1],X[i]+1,X[i+2],\ldots,X[K-1]$.

Für ein gegebenes Anfangsspielfeld ist das Ziel des Spielers, durch null oder mehr Verschmelzungsoperationen eine große Frucht zu erzeugen.

Zum Beispiel gilt auf dem Spielfeld $X=[2,1,1,3,2]$, dass $X[1]=X[2]$ ist. Die Wahl $i=1$ und eine Verschmelzung ändern das Spielfeld zu $X=[2,2,3,2]$. Weil $X[0]=X[1]$, ändern die Wahl $i=0$ und eine Verschmelzung es zu $X=[3,3,2]$. Schließlich ändern die Wahl $i=0$ und eine Verschmelzung wegen $X[0]=X[1]$ das Spielfeld zu $X=[4,2]$. So entsteht eine Frucht mit Kennnummer $4$, der größtmöglichen erreichbaren Kennnummer.

Gegeben ist eine Folge $A$ der Länge $N$. Ihre Elemente können sich ändern, und die Änderungen sind kumulativ. Jedes Mal, wenn ein ganzzahliges Paar $(l,r)$ mit $0\le l\le r\le N-1$ gegeben wird, musst du die größte auf dem Spielfeld $A[l],\ldots,A[r]$ erreichbare Fruchtkennnummer bestimmen. Insgesamt gibt es $Q$ Ereignisse, jeweils eine Elementänderung oder die Angabe eines Paars.

Implementierungsdetails

Du musst die folgenden Funktionen implementieren.

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

• $A$: ein ganzzahliges Array der Größe $N$.
• Diese Funktion wird genau einmal und vor allen anderen Funktionen aufgerufen.
• Benötigte Vorverarbeitung oder Initialisierung globaler Variablen für spätere Aufrufe kann in dieser Funktion implementiert werden.

int play_game(int l, int r)

• Diese Funktion muss die größte auf dem Spielfeld $A[l],\ldots,A[r]$ erreichbare Fruchtkennnummer zurückgeben.
• Diese Funktion wird mindestens einmal aufgerufen.

void update_game(int p, int v)

• Ändere den Wert von $A[p]$ zu $v$.

Die Gesamtzahl der Aufrufe von play_game und update_game ist $Q$.

An keiner Stelle des eingereichten Quellcodes dürfen Ein-/Ausgabefunktionen ausgeführt werden.

Hinweis

$A[i],\ldots,A[j]$ ist die Folge der Länge $j-i+1$, die aus den Elementen $i$ bis $j$ von $A$ besteht. Zum Beispiel ist für $A=[3,5,7,2,9]$ die Folge $A[1],\ldots,A[3]$ gleich $[5,7,2]$ und $A[4],\ldots,A[4]$ gleich $[9]$.

Beschränkungen

• $1\le N,Q\le100\,000$
• $1\le A[i]\le10$ ($0\le i\le N-1$).
• Für jeden Aufruf von play_game: $0\le l\le r\le N-1$.
• Für jeden Aufruf von update_game: $0\le p\le N-1$, $1\le v\le10$.

Teilaufgaben

1 (5 Punkte)

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

2 (6 Punkte)

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

3 (8 Punkte)

• $N\le4\,000$.
• $Q\le4\,000$.
• $A[i]\le2$ ($0\le i\le N-1$).
• Für jeden Aufruf von update_game: $v\le2$.

4 (15 Punkte)

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

5 (12 Punkte)

• $A[i]\le2$ ($0\le i\le N-1$).
• Für jeden Aufruf von update_game: $v\le2$.

6 (14 Punkte)

• update_game wird nicht aufgerufen.

7 (40 Punkte)

• Keine zusätzlichen Beschränkungen.

Beispiele

Beispiele 1

Betrachte den Fall $N=5$, $A=[2,1,1,3,4]$.

Der Grader ruft die folgenden Funktionen der Reihe nach auf.

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

Beispiele 2

Betrachte den Fall $N=7$, $A=[1,1,1,1,2,2,2]$.

Der Grader ruft die folgenden Funktionen der Reihe nach auf.

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

Beispielgrader

Der Beispielgrader liest Eingaben im folgenden Format.

• Zeile 1: $N$.
• Zeile 2: $A[0]\ A[1]\ \cdots\ A[N-1]$.
• Zeile 3: $Q$.
• Zeile $3+i$ ($1\le i\le Q$): 1 l r für einen Aufruf von play_game oder 2 p v für einen Aufruf von update_game.

Der Beispielgrader gibt Folgendes aus.

• Zeile $i$: der Rückgabewert des $i$-ten Aufrufs von play_game.

Beachte, dass der Beispielgrader vom bei der tatsächlichen Bewertung verwendeten Grader abweichen kann.