설국

”국경의 긴 터널을 빠져나오자, 월향이었다.”

월향은 $1$번 도시부터 $N$번 도시까지 총 $N$개의 도시가 일렬로 나열된 아름다운 눈의 고장이다. 현재 $i$번 도시에는 $A\_{i}$만큼의 눈이 쌓여있다. $l$번 도시부터 $r$번 도시까지를 제설한다는 것은, $A\_{l}=A\_{l+1}=\cdots =A\_{r}$이 되도록 제설기를 적절히 사용하는 것이다. 제설기를 한번 사용해 아래와 같은 작업을 할 수 있다.

• $l\leq p\<r$이고 $A\_{p}$와 $A\_{p+1}$이 전부 $1$ 이상인 정수 $p$를 골라, $A\_{p}$와 $A\_{p+1}$을 각각 $1$씩 감소시킨다.

월향의 제설 담당자인 당신은 다음 두 가지 쿼리를 처리해야 한다.

• $1$ $i$ $v$: $i$번 도시에 쌓인 눈의 양이 $v$로 변경된다. $(1\leq i\leq N;0\leq v\leq 10^9)$
• $2$ $l$ $r$: $l$번 도시부터 $r$번 도시까지를 제설하기 위해 필요한 제설기 사용횟수의 최솟값을 출력한다. 불가능하다면 -1을 출력한다. $(1\leq l\<r\leq N)$

첫째 줄에 도시의 개수 $N$이 주어진다. $(2 \leq N \leq 200\ 000)$

다음 줄에 각 도시에 쌓인 눈의 양을 나타내는 정수 $A\_{1}, A\_{2}, \cdots , A\_{N}$이 공백으로 구분되어 주어진다. $(0 \leq A\_{i} \leq 10^9)$

다음 줄에 쿼리의 개수 $Q$가 주어진다. $(1 \leq Q \leq 200\ 000)$

다음 $Q$개의 줄에 걸쳐 각 쿼리가 주어진다.

$2$ $l$ $r$ 쿼리는 하나 이상 주어진다.

각각의 $2$ $l$ $r$ 쿼리에 대해 답을 한 줄에 하나씩 주어진 순서대로 출력한다.