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 ith month (1 ≤ i ≤ N), he has received some non-negative 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 Lth month at the university and ends at the Rth. 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[R-L+1] - S[R-L])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*104
- 0 ≤ A[i] ≤ 106

-----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
5

Explanation

The first query: sorted array looks like (1, 2, 3, 4, 5) and the answer is calculated as (2-1)2 + (3-2)2 + (4-3)2 + (5-4)2 = 4

The second query: sorted array looks like (1, 2, 3, 4) and the answer is calculated as (2-1)2 + (3-2)2 + (4-3)2 = 3

The last query: sorted array looks like (2, 4, 5) and the answer is calculated as (4-2)2 + (5-4)2 = 5

Difficulty: interview

Starter code:

Solutions:
n=eval(input())
grades=list(map(int,input().split()))
m=eval(input())
for df in range(m):
 x,y=list(map(int,input().split()))
 arr=[]
 arr=grades[x-1:y]
 arr.sort()
 sum=0
 #arr.append(1000000)
 for nh in range(0,len(arr)-1,1):
  sum=sum+(arr[nh+1]-arr[nh])**2
  #print sum,len(arr),nh+1,nh
 print(sum)

n = eval(input())
gr = [int(i) for i in input().split()]
q = eval(input())
for _ in range(q):
 l,r = list(map(int,input().split()))
 temp = gr[l-1:r]
 temp.sort()
 ans = 0
 l = len(temp)
 for i in range(l-1):
  x = temp[i]
  y = temp[i+1]
  ans += (x-y)*(x-y)
 print(ans)


n=eval(input())
grades=list(map(int,input().split()))

m=eval(input())
main=[]
for df in range(m):
 x,y=list(map(int,input().split()))
 arr=[]
 arr=grades[x-1:y]
 arr.sort()
 sum=0
 #arr.append(1000000)
 for nh in range(0,len(arr)-1,1):
  sum=sum+(arr[nh+1]-arr[nh])*(arr[nh+1]-arr[nh])
  #print sum,len(arr),nh+1,nh
 print(sum)

n,a,m=eval(input()),list(map(int,input().split())),eval(input())
for i__i in range(m):
 l,r= list(map(int,input().split()))
 l-=1
 Rev,_=a[l:r],0
 Rev.sort()
 d=len(Rev)
 for i_i in range(0,d-1):
  _+=(Rev[i_i+1]-Rev[i_i])*(Rev[i_i+1]-Rev[i_i])
 print(_)


MOD = 10**9+7
faltu = eval(input())
theList = list(map(int,input().split()))
tcase = eval(input())
for times in range(tcase):
 left, right = list(map(int,input().split()))
 sub = sorted(theList[left-1:right])
 sol = 0
 for index in range(1,right-left+1):
  sol += (sub[index] - sub[index-1])**2
 print(sol)

N = eval(input())
import math
arr=list(map(int,input().split()))
M=eval(input())
for iI in range(M):
 L,R=list(map(int,input().split()))
 su=0
 ok = arr[L-1:R]
 #print ok
 aks=len(ok)
 ok.sort()
 for ii in range(0,aks-1):
  su=su+(math.pow((ok[ii+1]-ok[ii]),2))
 print(int(su)) 
 
 


n=int(input())
m=list(map(int,input().split()))
q=int(input())
for case in range(q):
 l,r=list(map(int,input().split()))
 l=l-1
 r=r-1
 s=m[l:r+1]
 s.sort()
 ans=0
 for i in range(r-l):
  ans=ans+(s[i+1]-s[i])**2
 print(ans)


n=int(input())
a=list(map(int,input().split()))
m=int(input())
for i in range(0,m):
 l,r=list(map(int,input().split()))
 b=a[l-1:r]
 b.sort()
 le=len(b)
 sum=0
 for j in range(1,le):
  sum+=((b[j]-b[j-1])**2)
 
 print(sum)

def qsort(inlist):
 if inlist == []:
  return []
 else:
  pivot = inlist[0]
  lesser = qsort([x for x in inlist[1:] if x < pivot])
  greater = qsort([x for x in inlist[1:] if x >= pivot])
  return lesser + [pivot] + greater

n=eval(input())
a=list(map(int,input().split()))
for i in range(eval(input())):
 l,r=(int(x) for x in input().split())
 b=a[l-1:r]
 c=[]
 c=qsort(b)
 sum=0
 for i in range(1,len(c)):
  j=c[i]-c[i-1]
  sum+=pow(j,2)
 print(sum)


import sys

n = eval(input())
lists = list(map(int,sys.stdin.readline().split()))
for __ in range(eval(input())) :
 l , r = [x-1 for x in list(map(int,sys.stdin.readline().split()))]
 k = [i for i in sorted(lists[l:r+1])]
 ans = 0
 for i in range(1,len(k)) :
  ans += (k[i-1]-k[i])**2
 print(ans)


n=int(input())
li=list(map(int, input().split()))
m=int(input())
for i in range(m):
 l, r = list(map(int, input().split()))
 temp = li[l-1:r]
 temp.sort()
 ans=0
 for j in range(1, len(temp)):
  ans+=(temp[j]-temp[j-1])**2
 print(ans)

n=eval(input())
a=list(map(int,input().split()))
for i in range(eval(input())):
 l,r=(int(x) for x in input().split())
 b=a[l-1:r]
 b.sort()
 sum=0
 for i in range(1,len(b)):
  j=b[i]-b[i-1]
  sum+=pow(j,2)
 print(sum)


n=int(input())
g=[int(x) for x in input().split()]
m=int(input())
while(m>0):
 q=[int(x) for x in input().split()]
 k=g[q[0]-1:q[1]]
 k.sort()
 s=0
 for i in range(0,len(k)-1):
  s+=(k[i+1]-k[i])**2
 print(s)
 m-=1

import sys

n = int(sys.stdin.readline())
l = list(map(int,sys.stdin.readline().split()))

for cases in range(int(sys.stdin.readline())):
 L, R = list(map(int,sys.stdin.readline().split()))
 List = sorted(l[L-1:R])
 ans = 0
 for i in range(1,len(List)):
  ans += (List[i]-List[i-1])**2
 print(ans) 


x = eval(input())
a = list(map(int, input().split()))
q = eval(input())
for __ in range(q):
 l, r = list(map(int, input().split()))
 l-=1
 R = sorted(a[l:r])
 x = 0
 for ii in range(1,len(R)):
  x+=(R[ii]-R[ii-1])**2
 print(x)


n=int(input())
a=list(map(int,input().split()))
for q in range(int(input())):
 l,r=list(map(int,input().split()))
 s=sorted(a[l-1:r])
 ans=0
 for i in range(r-l):
  ans+=(s[i+1]-s[i])**2
 print(ans)

n=eval(input())
a=input().split()
for i in range(n):
 a[i]=int(a[i])
m=eval(input())
for i in range(m):
 l,r=input().split()
 l=int(l)-1
 r=int(r)
 s=a[l:r]
 s.sort()
 sum=0
 for i in range(1,r-l):
  sum+=(s[i]-s[i-1])**2
  
 print(sum)