나비와 전봇대 (Hard)

나비는 새로 건설할 도시의 전봇대를 관리하는 일을 맡았다. 아직 전선이 연결되지 않았기 때문에, 나비는 이 전봇대들의 전선을 연결해야 한다. 전봇대는 $1$의 간격으로 직선을 따라 총 $N$개가 건설되어 있으며 왼쪽에서부터 번호가 $1$부터 $N$까지 붙어 있다. 첫 번째 전봇대의 위치는 $1$이고 초기에 $i$번 전봇대의 높이는 $H_i$이다. 좌표평면에서 나타낸다면 $i$번 전봇대는 $(i,0)$부터 $(i,H_i)$를 연결하는 선분으로 생각할 수 있다.

전선은 두 전봇대의 가장 윗부분을 최단 거리로 연결한다. 즉 $i$번째 전봇대와 $j$번째 전봇대가 연결된다면 $(i,H_i)$와 $(j,H_j)$를 선분으로 연결한다. 그리고 이때 연결 비용은 전선의 길이의 제곱이다.

나비는 준혁이에게 시작 전봇대의 번호 $p$를 받고 $p$번 전봇대를 포함하여 몇 개의 전봇대를 선택하여 전선을 연결한다. 선택한 전봇대를 번호의 오름차순으로 정렬하였을 때 $S_1, S_2, \ldots, S_k$라 한다면 $S_i$번째 전봇대와 $S_{i+1}$번째 전봇대를 전선으로 연결하게 된다. $(1\le i<k)$

또한 나비는 다음과 같은 조건을 만족하도록 전봇대를 선택하여 연결하여야 한다.

• 나비가 연결한 전선과 전봇대가 교차해선 안 된다. 단, 전선이 어떤 전봇대 $i$와 $(i,H_i)$에서 만나는 것은 가능하다.
• $p$를 기준으로 왼쪽으로 갈수록 선택한 전봇대의 높이가 단조증가하고, $p$를 기준으로 오른쪽으로 갈수록 선택한 전봇대의 높이가 단조증가하여야 한다. 즉 $S_t = p$일 때 $H_{S_1} \ge H_{S_2} \ge \cdots \ge H_{S_{t-1}} \ge H_p \le H_{S_{t+1}} \le H_{S_{t+2}} \le \cdots \le H_{S_k}$를 만족해야 한다.
• 나비는 연결한 전선의 길이 합이 최대가 되도록 전선을 연결하려고 한다. 만약 그런 경우가 여러 가지 있다면, 연결 비용의 합이 최소인 방법으로 연결한다.

도시는 아직 건설중이라 계획 변경으로 인해 전봇대의 높이가 바뀔 수 있다. 준혁이는 나비에게 $Q$개의 작업을 준다. 작업에 따라 전봇대의 높이를 변경하거나 나비가 전선을 연결하기 시작할 시작 전봇대가 주어졌을 때 연결 비용의 합이 얼마인지 구해보자.

첫째 줄에 $N$이 주어진다. $(1 \le N \le 250\,000)$

둘째 줄에 정수 $H_1, H_2, ... ,H_N$이 공백으로 구분되어 주어진다. $(1 \le H_i \le 10^6)$

셋째 줄에 작업의 수 $Q$가 주어진다. $(1 \le Q \le 250\,000)$

넷째 줄부터 $Q$개의 줄에 걸쳐 작업을 나타내는 두 정수 $a$ $b$가 공백으로 구분되어 주어진다.

• 만약 $a$가 $0$이라면, 시작 전봇대의 번호가 $b$일 때(즉, $p = b$일 때) 연결 비용의 합을 출력한다. $(1\le b \le N)$
• 그렇지 않다면, $a$번 전봇대의 높이를 $b$로 변경한다. $(1\le b \le10^6)$

$a$가 $0$일 때마다 $p = b$일 때 연결 비용의 합을 한 줄에 하나씩 출력한다.