Kuriyama Mirai has killed many monsters and got many (namely n) stones. She numbers the stones from 1 to n. The cost of the i-th stone is v_{i}. Kuriyama Mirai wants to know something about these stones so she will ask you two kinds of questions:  She will tell you two numbers, l and r (1 ≤ l ≤ r ≤ n), and you should tell her $\sum_{i = l}^{r} v_{i}$.  Let u_{i} be the cost of the i-th cheapest stone (the cost that will be on the i-th place if we arrange all the stone costs in non-decreasing order). This time she will tell you two numbers, l and r (1 ≤ l ≤ r ≤ n), and you should tell her $\sum_{i = l}^{r} u_{i}$. 

For every question you should give the correct answer, or Kuriyama Mirai will say "fuyukai desu" and then become unhappy.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 10^5). The second line contains n integers: v_1, v_2, ..., v_{n} (1 ≤ v_{i} ≤ 10^9) — costs of the stones. 

The third line contains an integer m (1 ≤ m ≤ 10^5) — the number of Kuriyama Mirai's questions. Then follow m lines, each line contains three integers type, l and r (1 ≤ l ≤ r ≤ n; 1 ≤ type ≤ 2), describing a question. If type equal to 1, then you should output the answer for the first question, else you should output the answer for the second one.


-----Output-----

Print m lines. Each line must contain an integer — the answer to Kuriyama Mirai's question. Print the answers to the questions in the order of input.


-----Examples-----
Input
6
6 4 2 7 2 7
3
2 3 6
1 3 4
1 1 6

Output
24
9
28

Input
4
5 5 2 3
10
1 2 4
2 1 4
1 1 1
2 1 4
2 1 2
1 1 1
1 3 3
1 1 3
1 4 4
1 2 2

Output
10
15
5
15
5
5
2
12
3
5



-----Note-----

Please note that the answers to the questions may overflow 32-bit integer type.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
v = list(map(int, input().split()))
u = sorted(v)
dv, du = [0] * (n + 1), [0] * (n + 1)
ans = list()

for i in range(1, n + 1):
    dv[i] = dv[i-1] + v[i-1]
    du[i] = du[i-1] + u[i-1]

for i in range(int(input())):
    (t, l, r) = list(map(int, input().split()))
    d = dv if t == 1 else du
    ans.append(str(d[r] - d[l-1]))

print('\n'.join(ans))


n = int(input().strip())
v = list(map(int, input().split()))
m = int(input().strip())
f1 = [0] * n
f2 = [0] * n
u = sorted(v)
for i in range(n):
    f1[i] = v[i]
    if i > 0:
        f1[i] += f1[i - 1]
        
for i in range(n):
    f2[i] = u[i]
    if i > 0:
        f2[i] += f2[i - 1]        

ans = []

for i in range(m):
    t, l, r = map(int, input().split())
    l -= 1
    r -= 1
    if t == 1:
        an = f1[r]
        if l > 0:
            an -= f1[l - 1]
        ans.append(an)
    else:
        an = f2[r]
        if l > 0:
            an -= f2[l - 1]
        ans.append(an)
        
print(*ans, sep = '\n')

import sys, itertools
f = sys.stdin
# f = open('H:\\Portable Python 3.2.5.1\\tests\\test_248B1.txt') 
n = int(f.readline().strip())
v = [int(u) for u in f.readline().strip().split()]
m = int(f.readline().strip())

vs = list(itertools.accumulate(v))
u = sorted(v)
us = list(itertools.accumulate(u))

p = []
for i in range(m):
    type, l, r = list(map(int, f.readline().strip().split()))
    if type==1:
        if l>1 :p.append( str(vs[r-1]-vs[l-2]) )
        else :p.append( str(vs[r-1]) )
    else:
        if l>1 :p.append( str(us[r-1]-us[l-2]) )
        else :p.append( str(us[r-1]) )

print('\n'.join(p))


from sys import stdin as cin

n = int(cin.readline())
a=list((list(map(int,cin.readline().split()))))

b = sorted(a)

for i in range(1,n):
    a[i]+=a[i-1]
    b[i]+=b[i-1]
for i in range(int(cin.readline())):
    q,x,y=(list(map(int,cin.readline().split())))
    #print(q,x,y)
    if q==1:
        if x==1:
            print(a[y-1]-a[x-1]+a[0])
        else:
            print(a[y-1]-a[x-2])
    else:
        if x==1:
            print(b[y-1]-b[x-1]+b[0])
        else:
            print(b[y-1]-b[x-2])



n = int(input())
a = list(map(int, input().split()))
b = sorted(a)

prefa = [0] * (n + 1)
prefb = [0] * (n + 1)

for i in range(1, n + 1):
	prefa[i] = prefa[i - 1] + a[i - 1]

for i in range(1, n + 1):
	prefb[i] = prefb[i - 1] + b[i - 1]

m = int(input())
for i in range(m):
	type, l, r = map(int, input().split())
	if type == 1:
		print(prefa[r] - prefa[l - 1])
	else:
		print(prefb[r] - prefb[l - 1])

n=int(input())
rocks=list(map(int, input().split()))
sortrocks=[0]*n
for i in range(n):
    sortrocks[i]=rocks[i]
sortrocks.sort()
v=[0]*(n+1)
v[1]=rocks[0]
u=[0]*(n+1)
u[1]=sortrocks[0]
for i in range(2,n+1):
    v[i]=v[i-1]+rocks[i-1]
    u[i]=u[i-1]+sortrocks[i-1]
m=int(input())
for i in range(m):
    (type,l,r)=list(map(int, input().split()))
    l-=1
    if type==1:
        print(v[r]-v[l])
    else:
        print(u[r]-u[l])


n=int(input())

L=list(map(int,input().split()))
S=list(L)
for i in range(1,n):
    S[i]+=S[i-1]

X=list(sorted(L))
for i in range(1,n):
    X[i]+=X[i-1]
q=int(input())

while(q):
    q-=1
    t,x,y=list(map(int,input().split()))
    if(t==1):
        ans=S[y-1]
        if(x>1):
            ans-=S[x-2]
    else:
        ans=X[y-1]
        if(x>1):
            ans-=X[x-2]
    print(ans)


n = int(input())
price = list(map(int,input().split()))
price_s = list(price)
price_s.sort()
m = int(input())
pre_sum = [price[0]]
pre_sum1 = [price_s[0]]

out = []

for i in range(1,n,1):
    ele = price[i] + pre_sum[i-1]

    
    pre_sum.append(ele)
    ele1 = price_s[i] + pre_sum1[i-1]
    pre_sum1.append(ele1)
#print(pre_sum)
#print(pre_sum1)
for i in range(m):
    full = False
    curr = list(map(int,input().split()))
    ind1 = curr[2] -1
    
    ind2 = curr[1] - 2
    if ind2 < 0 :
        full = True
    if curr[0] == 1 :
        if full :
            out.append(pre_sum[ind1])
        else:
            
            lis1 = pre_sum[ind1]
            lis2 = pre_sum[ind2]
            out.append(lis1-lis2)
    else:
        if full :
            out.append(pre_sum1[ind1])
        else:
            
            lis1 = pre_sum1[ind1]
            lis2 = pre_sum1[ind2]
            out.append(lis1-lis2)
for i in range(m):
    print(out[i])


n = int(input())
us = list(map(int, input().split(" ")))
os = us[:]
os.sort()

for i in range(1,len(os)):
    os[i] += os[i-1]
    us[i] += us[i-1]
os = [0]+os
us = [0]+us

res = []

q = int(input())
for i in range(q):
    t, l, r = list(map(int, input().split(" ")))
    if t == 1:
        res.append(str(us[r] - us[l-1]))
    else:
        res.append(str(os[r] - os[l-1]))


print("\n".join(res))

count = int(input())
v = [int(c) for c in input().split()]
vsort = v[:]
vsort.sort()
sumV = [0,v[0]]
sumVS = [0,vsort[0]]
for i in range(1,count):
    sumV.append(sumV[i]+v[i])
    sumVS.append(sumVS[i]+vsort[i])

qc = int(input())

for x in range(qc):
    q = [int(c) for c in input().split()]
    if q[0] == 1:
        tmp = sumV
    else:
        tmp = sumVS
    print(tmp[q[2]] - tmp[q[1] - 1])

n = int(input())
I = list(map(int, input().split()))
P = sorted(I)

sI = [0] * (n + 1)
sP = [0] * (n + 1)

for i in range(1, n + 1):
    sI[i] = sI[i-1] + I[i-1]
    sP[i] = sP[i-1] + P[i-1]

m = int(input())

for i in range(m):
    t, l, r = list(map(int, input().split()))
    if t == 1:
        print(sI[r] - sI[l-1])
    else:
        print(sP[r] - sP[l-1])



n = int(input())
v1 = list(map(int, input().split()))
v2 = sorted(v1)
v1, v2 = [0] + v1, [0] + v2
for i in range(1, n + 1):
    v2[i] += v2[i - 1]
    v1[i] += v1[i - 1]
m = int(input())
for i in range(m):
    t, l, r = map(int, input().split())
    if t == 1:
        print (v1[r] - v1[l - 1])
    else:
        print (v2[r] - v2[l - 1])

R = lambda:map(int, input().split())
n = int(input())
v = list(R())
s = [[0] * (n + 1)]
for i in range(n):
  s[0][i + 1] = s[0][i] + v[i]
v = sorted(v)
s += [[0] * (n + 1)]
for i in range(n):
  s[1][i + 1] = s[1][i] + v[i]
m = int(input())
print("\n".join(map(str, (s[t - 1][r] - s[t - 1][l - 1] for t, l, r in (R() for _ in range(m))))))

R = lambda:map(int, input().split())
n = int(input())
a = [0] + list(R())
s = [a, sorted(a)]
for i in range(n):
  s[0][i + 1] += s[0][i]
  s[1][i + 1] += s[1][i]
m = int(input())
print("\n".join(map(str, (s[t - 1][r] - s[t - 1][l - 1] for t, l, r in (R() for _ in range(m))))))

n, u = int(input()), list(map(int, input().split()))
v = list(sorted(u))
for i in range(n - 1): 
    u[i + 1] += u[i]
    v[i + 1] += v[i]
u, v = [0] + u, [0] + v
for i in range(int(input())):
    t, l, r = map(int, input().split())
    print(u[r] - u[l - 1] if t == 1 else v[r] - v[l - 1])

n = int(input())
tab = [int(x) for x in input().split(' ')]
stab = tab.copy()
stab.sort()
sumtab = [0,tab[0]]
sumstab = [0,stab[0]]
for x in range(2,len(tab)+1):
    sumtab.append(sumtab[x-1]+tab[x-1])
for x in range(2,len(stab)+1):
    sumstab.append(sumstab[x-1]+stab[x-1])
m = int(input())
for i in range(m):
    query = [int(x) for x in input().split(' ')]
    if query[0]==1:
        print(sumtab[query[2]] - sumtab[query[1]-1])
    else:
        print(sumstab[query[2]] - sumstab[query[1]-1])


n = int(input())
v = list(map(int,input().split()))
m = int(input())
i = 0
u = list(v)
u.sort()
while i < n-1:
    v[i+1] += v[i];
    u[i+1] += u[i];
    i += 1
u, v = [0] + u, [0] + v
i = 0
while i < m:
    t, l, r = map(int,input().split())
    if t == 1: print(v[r] - v[l-1])
    else: print(u[r] - u[l-1])
    i += 1;

n = int(input())
v = list(map(int, input().split()))
a = [0 for i in range(n)]
a[0] = v[0]
for i in range(1, n):
    a[i] = a[i - 1] + v[i]
a += [0]
v = sorted(v)
b = [0 for i in range(n)]
b[0] = v[0]
for i in range(1, n):
    b[i] = b[i - 1] + v[i]
b += [0]
m = int(input())
for i in range(m):
    t, l, r = list(map(int, input().split()))
    if t - 1:
        print(b[r - 1] - b[l - 2])
    else:
        print(a[r - 1] - a[l - 2])


import sys
#Never really use this value
numberOfStones = int(sys.stdin.readline())
#Stones in given order
stonelistV = (list(map(int, sys.stdin.readline().split())))
#stones in ascending order
stonelistU = sorted(stonelistV)
#print(stonelistU)
#Hold the computed sums
du = [0] * 1
dv = [0] * 1
#Compute the sums
for stone in stonelistV:
    dv.append(dv[-1] + stone)
for stone in stonelistU:
    du.append(du[-1] + stone)

numberOfQuestions = int(sys.stdin.readline())
for q in range(numberOfQuestions):
    questions = list(map(int, sys.stdin.readline().split()))
    if questions[0] == 1:
        answer = dv[questions[2]] - dv[questions[1] - 1]
    if questions[0] == 2:
        answer = du[questions[2]] - du[questions[1] - 1]
    print(answer)

stones = int(input())
costs = list(map(int, input().split(' ')))
reg = costs[:]
costs.sort()
a = [0] + [0] * stones
b = [0] + [0] * stones
for i in range(1, stones + 1):
    a[i] = a[i-1] + costs[i-1]
    b[i] = b[i-1] + reg[i-1]
    
for i in range(int(input())):
    x, y, z = list(map(int, input().split(' ')))
    if x == 2:
        print(a[z] - a[y-1])
    else:
        print(b[z] - b[y-1])


n,num=int(input()),list(map(int,input().split()))
sort=list(sorted(num))
for i in range(n-1):
    num[i+1]+=num[i]
    sort[i+1]+=sort[i]
num,sort=[0]+num,[0]+sort
for i in range(int(input())):
    t,l,r=list(map(int,input().split()))
    print(num[r]-num[l-1] if t==1 else sort[r]-sort[l-1])


n=int(input())
lis=input().split()
for i in range(n):
    lis[i]=int(lis[i])
lis2=sorted(lis)
m=int(input())
lis1=[]
for i in range(m):
    lis1.append(input().split())
for i in range(m):
    for j in range(3):
        lis1[i][j]=int(lis1[i][j])

s=[lis[0]]
for i in range(1,n):
    s.append(lis[i]+s[i-1])
s=[0]+s
s2=[lis2[0]]
for i in range(1,n):
    s2.append(lis2[i]+s2[i-1])
s2=[0]+s2

for i in range(m):
    if lis1[i][0]==1:
        print(s[lis1[i][2]]-s[lis1[i][1]-1])
    else:
        print(s2[lis1[i][2]]-s2[lis1[i][1]-1])


n = int(input())
v = [int(x) for x in input().split()]
u = sorted(v)
m = int(input())
for i in range(1, n):
	v[i] += v[i - 1]
	u[i] += u[i - 1]
v.append(0)
u.append(0)
for i in range(m):
	t, l, r = [int(x) for x in input().split()]
	if t == 1:
		print(v[r - 1] - v[l - 2])
	else:
		print(u[r - 1] - u[l - 2])


def main():
    input()
    vv = list(map(int, input().split()))
    uu = sorted(vv)
    for tmp in vv, uu:
        a = 0
        for i, b in enumerate(tmp):
            tmp[i] = a
            a += b
        tmp.append(a)
    res = []
    vu = (None, vv, uu)
    for _ in range(int(input())):
        type, l, r = list(map(int, input().split()))
        tmp = vu[type]
        res.append(str(tmp[r] - tmp[l - 1]))
    print('\n'.join(res))


def __starting_point():
    main()

__starting_point()