나비와 전봇대 (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$라 하면, $1 \le i < k$인 모든 $i$에 대해 $S_i$번 전봇대와 $S_{i+1}$번 전봇대를 전선으로 잇는다.

나비는 다음 조건을 만족하도록 전봇대를 고르고 연결해야 한다.

• 연결한 전선은 전봇대와 교차해서는 안 된다. 다만 전선이 어떤 전봇대 $i$의 꼭대기 $(i,H_i)$에서 만나는 것은 가능하다.
• $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, \ldots, 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 \le 10^6)$

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