과일 게임

과일 게임은 여러 가지 종류의 과일들을 합쳐 크기가 큰 종류의 과일을 만드는 게임이다. 과일 게임의 게임판은 수열 $X[0], X[1], \cdots , X[K - 1]$로 표현할 수 있다. 이 때 각 수는 과일의 종류에 따른 번호를 나타내며, 번호가 클수록 과일의 크기가 크다는 것을 의미한다.

이 때 플레이어는 종류가 같으며 인접한 두 과일을 합쳐서 크기가 큰 과일을 만들 수 있는 합치기 연산을 수행할 수 있다. 이 연산은 다음과 같이 정의된다.

합치기: $X[0], X[1], \cdots , X[K - 1]$로 표현되는 게임판에서 정수 $0 ≤ i ≤ 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$의 원소는 중간에 변경될 수 있으며 이 변화는 누적된다. 여러분은 $0 ≤ l ≤ r ≤ N - 1$을 만족하는 정수 순서쌍 $(l, r)$이 주어질 때마다 $A[l], \cdots , A[r]$로 표현되는 게임판에서 얻을 수 있는 가장 큰 과일의 번호를 구하는 프로그램을 작성해야 한다. 수열의 원소가 변하거나 순서쌍이 주어지는 횟수는 총 $Q$번이다.

문제

제한