33513번 - 설국

문제

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

월향은 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$ 쿼리에 대해 답을 한 줄에 하나씩 주어진 순서대로 출력한다.

제한

힌트