과일 게임

과일 게임은 여러 가지 종류의 과일을 합쳐 더 큰 종류의 과일을 만드는 게임이다. 게임판은 수열 $X[0], X[1], \cdots, X[K-1]$로 나타낼 수 있다. 각 수는 과일의 종류를 나타내는 번호이며, 번호가 클수록 과일의 크기가 크다.

플레이어는 합치기 연산을 수행할 수 있다. 같은 종류이면서 인접한 두 과일을 합쳐 더 큰 과일을 만드는 연산이다. 연산은 다음과 같이 정의된다.

합치기: 게임판 $X[0], X[1], \cdots, X[K-1]$에서 정수 $0 \le i \le K-2$를 골라 $X[i] = X[i+1]$을 만족하면, 게임판을 $X[0], \cdots, X[i-1], X[i]+1, X[i+2], \cdots, X[K-1]$로 바꾼다.

플레이어의 목표는 초기 게임판이 주어졌을 때 합치기 연산을 0회 이상 사용하여 크기가 큰 과일을 만드는 것이다.

예를 들어 게임판이 $X = [2, 1, 1, 3, 2]$인 경우를 보자. $X[1] = X[2]$이므로 $i = 1$을 골라 연산을 수행하면 게임판은 $X = [2, 2, 3, 2]$가 된다. 또 $X[0] = X[1]$이므로 $i = 0$을 골라 연산을 수행하면 $X = [3, 3, 2]$가 된다. 마지막으로 $X[0] = X[1]$이므로 $i = 0$을 골라 연산을 수행하면 $X = [4, 2]$가 된다. 이렇게 하면 번호가 4인 과일을 만들 수 있고, 이것이 얻을 수 있는 가장 큰 과일의 번호이다.

길이 $N$의 수열 $A$가 주어진다. $A$의 원소는 중간에 변경될 수 있으며, 이 변화는 누적된다. 정수 순서쌍 $(l, r)$이 $0 \le l \le r \le N-1$을 만족하며 주어질 때마다, $A[l], \cdots, A[r]$로 표현되는 게임판에서 얻을 수 있는 가장 큰 과일의 번호를 구하는 프로그램을 작성해야 한다. 수열의 원소가 변하거나 순서쌍이 주어지는 횟수는 총 $Q$번이다.

• $1 \le N, Q \le 100\,000$
• 모든 $i$에 대해 $1 \le A[i] \le 10$ ($0 \le i \le N-1$)
• 모든 play_game 호출에 대해 $0 \le l \le r \le N-1$
• 모든 update_game 호출에 대해 $0 \le p \le N-1$, $1 \le v \le 10$