나비와 전봇대 (Easy)

나비는 새로 건설할 도시의 전봇대를 관리하는 일을 맡았다. 아직 전선이 연결되지 않았으므로, 나비는 이 전봇대들 사이에 전선을 연결해야 한다. 전봇대는 간격 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$개의 작업을 준다. 작업마다 시작 전봇대가 $p$일 때, 조건을 만족하면서 연결 비용 합의 최솟값을 구한다.

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

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

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

넷째 줄부터 $Q$개의 줄에 걸쳐 시작 전봇대의 번호 $p$가 주어진다. ($1 \le p \le N$)

줄마다 시작 전봇대의 번호가 $p$일 때 연결 비용의 합을 한 줄에 하나씩 출력한다.