Estimating progress

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian
Leha is a usual student at 'The Usual University for Usual Students'. Sometimes he studies hard; at other times he plays truant and gets busy with other things besides academics. He has already studied at the university for N months. For the i^{th} month (1 ≤ i ≤ N), he has received some nonnegative integer grade A[i].
Now he wants to analyse his progress for some periods of his university education. An arbitrary period, defined by two positive integers L and R, begins at Leha's L^{th} month at the university and ends at the R^{th}. The analysis is performed via the following steps.
1. Write down all the grades for each month from L to R and sort them. Let's call the sorted list S.
2. Calculate the sum of squared differences of consecutive elements in S, that is, (S[2]  S[1])^{2} + (S[3]  S[2])^{2} + ... + (S[RL+1]  S[RL])^{2}.
Input
The first line contains one integer N — the number of months Leha has already studied at the university.
The second line contains N integers — list A of Leha's grades.
The third line contains one integer M — the number of periods Leha is interested in analyzing.
Each of the following M lines contain two integers L and R describing each period.
Output
For each query, output one integer — the result of the progress analysis for the corresponding period.
Constraints
 1 ≤ N, M ≤ 5*10^{4}
 0 ≤ A[i] ≤ 10^{6}
Subtasks
 Subtask 1 (19 points) 1 ≤ N, M ≤ 200, time limit = 2 sec
 Subtask 2 (31 points) 1 ≤ N, M ≤ 10 000, time limit = 2 sec
 Subtask 3 (26 points) 0 ≤ A[i] ≤ 100, time limit = 5 sec
 Subtask 4 (24 points) no additional constraints, , time limit = 5 sec
Example
Input: 5 1 3 2 4 5 5 1 5 1 4 2 4 3 3 3 5 Output: 4 3 2 0 5Explanation
The first query: sorted array looks like (1, 2, 3, 4, 5) and the answer is calculated as (21)^{2} + (32)^{2} + (43)^{2} + (54)^{2} = 4
The second query: sorted array looks like (1, 2, 3, 4) and the answer is calculated as (21)^{2} + (32)^{2} + (43)^{2} = 3
The last query: sorted array looks like (2, 4, 5) and the answer is calculated as (42)^{2} + (54)^{2} = 5
Author:  pavel1996 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/STDPRGS 
Tags  ltime29, mediumhard, moalgorithm, pavel1996 
Date Added:  28092015 
Time Limit:  2  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 