Gra w owoce polega na łączeniu owoców różnych rodzajów, aby tworzyć większe rodzaje owoców. Planszę można przedstawić jako ciąg $X[0],X[1],\ldots,X[K-1]$. Każda liczba jest identyfikatorem rodzaju owocu, a większy identyfikator oznacza większy owoc.

Gracz może wykonywać operację łączenia dwóch sąsiednich owoców tego samego rodzaju w większy owoc. Operacja jest zdefiniowana następująco.

Łączenie: na planszy $X[0],X[1],\ldots,X[K-1]$ wybierz liczbę całkowitą $0\le i\le K-2$. Jeśli $X[i]=X[i+1]$, zastąp planszę przez $X[0],\ldots,X[i-1],X[i]+1,X[i+2],\ldots,X[K-1]$.

Celem gracza dla danej planszy początkowej jest utworzenie dużego owocu przez wykonanie zera lub więcej operacji łączenia.

Na przykład dla planszy $X=[2,1,1,3,2]$, ponieważ $X[1]=X[2]$, wybór $i=1$ i łączenie zmienia planszę na $X=[2,2,3,2]$. Ponieważ $X[0]=X[1]$, wybór $i=0$ i kolejne łączenie zmienia ją na $X=[3,3,2]$. Wreszcie, ponieważ $X[0]=X[1]$, wybór $i=0$ i łączenie daje $X=[4,2]$. W ten sposób powstaje owoc o identyfikatorze $4$, największym możliwym do uzyskania.

Dany jest ciąg $A$ długości $N$. Jego elementy mogą się zmieniać, a zmiany są kumulowane. Za każdym razem, gdy podano parę liczb całkowitych $(l,r)$ spełniającą $0\le l\le r\le N-1$, znajdź największy identyfikator owocu możliwy do uzyskania na planszy $A[l],\ldots,A[r]$. Łącznie występuje $Q$ zdarzeń, z których każde jest zmianą elementu lub podaniem pary.

Szczegóły implementacji

Zaimplementuj poniższe funkcje.

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

• $A$: tablica liczb całkowitych rozmiaru $N$.
• Ta funkcja jest wywoływana dokładnie raz, przed wszystkimi pozostałymi funkcjami.
• W tej funkcji można zaimplementować przetwarzanie wstępne lub inicjalizację zmiennych globalnych potrzebnych do późniejszych wywołań.

int play_game(int l, int r)

• Ta funkcja musi zwrócić największy identyfikator owocu możliwy do uzyskania na planszy $A[l],\ldots,A[r]$.
• Ta funkcja jest wywoływana co najmniej raz.

void update_game(int p, int v)

• Zmień wartość $A[p]$ na $v$.

Łączna liczba wywołań play_game i update_game wynosi $Q$.

W żadnej części przesłanego kodu źródłowego nie wolno wykonywać funkcji wejścia/wyjścia.

Uwagi

$A[i],\ldots,A[j]$ to ciąg długości $j-i+1$ składający się z elementów od $i$ do $j$ ciągu $A$. Na przykład, gdy $A=[3,5,7,2,9]$, $A[1],\ldots,A[3]$ to $[5,7,2]$, a $A[4],\ldots,A[4]$ to $[9]$.

Ograniczenia

• $1\le N,Q\le100\,000$
• $1\le A[i]\le10$ ($0\le i\le N-1$).
• Dla każdego wywołania play_game: $0\le l\le r\le N-1$.
• Dla każdego wywołania update_game: $0\le p\le N-1$, $1\le v\le10$.

Podzadania

1 (5 punktów)

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

2 (6 punktów)

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

3 (8 punktów)

• $N\le4\,000$.
• $Q\le4\,000$.
• $A[i]\le2$ ($0\le i\le N-1$).
• Dla każdego wywołania update_game: $v\le2$.

4 (15 punktów)

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

5 (12 punktów)

• $A[i]\le2$ ($0\le i\le N-1$).
• Dla każdego wywołania update_game: $v\le2$.

6 (14 punktów)

• update_game nie jest wywoływana.

7 (40 punktów)

• Brak dodatkowych ograniczeń.

Przykład

Przykład 1

Rozważmy przypadek $N=5$, $A=[2,1,1,3,4]$.

Grader wywołuje kolejno poniższe funkcje.

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

Przykład 2

Rozważmy przypadek $N=7$, $A=[1,1,1,1,2,2,2]$.

Grader wywołuje kolejno poniższe funkcje.

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

Przykładowy grader

Przykładowy grader czyta dane w poniższym formacie.

• Wiersz 1: $N$.
• Wiersz 2: $A[0]\ A[1]\ \cdots\ A[N-1]$.
• Wiersz 3: $Q$.
• Wiersz $3+i$ ($1\le i\le Q$): 1 l r dla wywołania play_game lub 2 p v dla wywołania update_game.

Przykładowy grader wypisuje następujące dane.

• Wiersz $i$: wartość zwrócona przez $i$-te wywołanie play_game.

Pamiętaj, że przykładowy grader może różnić się od gradera używanego podczas właściwego oceniania.