나비와 전봇대 (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$라 한다면 $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$개의 작업을 준다. 작업마다 시작 전봇대가 $p$일 때 조건을 만족하게 연결 비용의 합의 최솟값을 구해보자.

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

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

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

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

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