/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
問題文
整数列 X = (X_1, X_2, \dots, X_k) に対して、関数 f(X) を以下のように定義します。
- X を昇順にソートした数列を Y = (Y_1, Y_2, \dots, Y_k) とする。
- \displaystyle f(X) = \sum_{i=1}^{k-1}(Y_{i+1}-Y_i)^2 である。
整数列 A = (A_1, A_2, \dots, A_N) があります。以下の形式のクエリが Q 個与えられるので、順に処理してください。
- 整数 l, r が与えられる。B = (A_l, A_{l + 1}, \dots, A_r) として、f(B) を求める。
制約
- 入力は全て整数
- 1≤N≤2\times10^4
- 1≤A_i≤10^9
- 1≤Q≤10^5
- 各クエリについて、1≤l≤r≤N
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 \cdots A_N
Q
\text{Query}_1
\text{Query}_2
\vdots
\text{Query}_Q
ここで、\text{Query}_i は i 個目のクエリを表す。各クエリは以下の形式で与えられる。
l r
出力
Q 行出力せよ。i 行目には、i 個目のクエリに対する答えを出力せよ。
入力例 1
3 3 1 4 4 1 1 1 2 2 3 1 3
出力例 1
0 4 9 5
A = (3, 1, 4) です。
- 1 個目のクエリでは、B = (3) を昇順にソートすると (3) になるので、f(B) = 0 です。
- 2 個目のクエリでは、B = (3, 1) を昇順にソートすると (1, 3) になるので、f(B) = 4 です。
- 3 個目のクエリでは、B = (1, 4) を昇順にソートすると (1, 4) になるので、f(B) = 9 です。
- 4 個目のクエリでは、B = (3, 1, 4) を昇順にソートすると (1, 3, 4) になるので、f(B) = 5 です。
入力例 2
10 19 70 14 11 85 75 72 35 14 50 10 1 1 3 8 5 7 1 3 5 8 5 5 2 10 2 5 1 5 2 9
出力例 2
0 1928 109 2626 1478 0 1188 3370 2860 1788
Problem Statement
For an integer sequence X = (X_1, X_2, \dots, X_k), let us define a function f(X) as follows:
- Let Y = (Y_1, Y_2, \dots, Y_k) be the sequence obtained by sorting X in ascending order.
- Then, \displaystyle f(X) = \sum_{i=1}^{k-1}(Y_{i+1}-Y_i)^2.
We have an integer sequence A = (A_1, A_2, \dots, A_N). Given Q queries in the following format, process them in order.
- Given integers l and r, find f(B), where B = (A_l, A_{l + 1}, \dots, A_r).
Constraints
- All values in the input are integers.
- 1≤N≤2\times10^4
- 1≤A_i≤10^9
- 1≤Q≤10^5
- For each query, 1≤l≤r≤N.
Input
The input is given from Standard Input in the following format:
N
A_1 A_2 \cdots A_N
Q
\text{Query}_1
\text{Query}_2
\vdots
\text{Query}_Q
Here, \text{Query}_i denotes the i-th query. Each query is given in the following format:
l r
Output
Print Q lines. The i-th line should contain the answer to the i-th query.
Sample Input 1
3 3 1 4 4 1 1 1 2 2 3 1 3
Sample Output 1
0 4 9 5
We have A = (3, 1, 4).
- In the 1-st query, f(B) = 0, because sorting B = (3) in ascending order yields (3).
- In the 2-nd query, f(B) = 4, because sorting B = (3, 1) in ascending order yields (1, 3).
- In the 3-rd query, f(B) = 9, because sorting B = (1, 4) in ascending order yields (1, 4).
- In the 4-th query, f(B) = 5, because sorting B = (3, 1, 4) in ascending order yields (1, 3, 4).
Sample Input 2
10 19 70 14 11 85 75 72 35 14 50 10 1 1 3 8 5 7 1 3 5 8 5 5 2 10 2 5 1 5 2 9
Sample Output 2
0 1928 109 2626 1478 0 1188 3370 2860 1788