两种顺序的区间和

题目描述

给定数组 a。类型 1 的询问求原数组区间和；类型 2 的询问求排序后数组的区间和。两种询问的端点都是 1 开始且含端点。

输入格式

第一行 n；第二行 n 个整数；第三行 q；后续 q 行 type、l、r。

输出格式

每个询问输出对应的区间和。

数据范围

1≤n,q≤100000；1≤a_i≤10^9；type 为 1 或 2。

样例

6
353477312 497686170 736890268 646590290 160191314 603783712
66
1 3 5
1 6 6
1 4 6
2 1 5
1 5 5
2 4 5
2 2 6
1 5 5
2 6 6
1 5 5
2 3 4
2 5 5
2 4 6
1 3 5
2 2 5
1 3 4
2 3 4
1 4 6
1 3 5
1 2 3
2 3 4
1 2 3
2 1 4
2 6 6
2 1 6
2 2 5
2 2 5
1 3 6
1 4 4
1 2 3
2 6 6
2 3 6
1 5 6
1 5 6
1 6 6
1 5 5
2 1 6
2 4 5
1 2 2
1 2 3
1 5 5
2 4 5
2 1 1
1 2 5
2 5 6
1 1 6
2 2 2
1 4 4
2 6 6
2 6 6
2 4 4
2 2 6
1 1 6
1 6 6
2 2 5
1 2 2
2 5 5
1 1 6
1 1 4
1 3 3
1 2 3
2 5 5
2 3 3
1 4 6
1 5 6
2 4 4

1543671872
603783712
1410565316
2261728798
160191314
1250374002
2838427752
160191314
736890268
160191314
1101469882
646590290
1987264270
1543671872
2101537484
1383480558
1101469882
1410565316
1543671872
1234576438
1101469882
1234576438
1615138508
736890268
2998619066
2101537484
2101537484
2147455584
646590290
1234576438
736890268
2484950440
763975026
763975026
603783712
160191314
2998619066
1250374002
497686170
1234576438
160191314
1250374002
160191314
2041358042
1383480558
2998619066
353477312
646590290
736890268
736890268
603783712
2838427752
2998619066
603783712
2101537484
497686170
646590290
2998619066
2234644040
736890268
1234576438
646590290
497686170
1410565316
763975026
603783712

8
528920484 572876435 460083124 721204066 264644751 625042708 720418976 584964617
99
2 2 4
2 4 6
2 6 8
1 4 7
1 4 5
2 5 7
2 3 4
2 1 7
1 1 7
2 6 7
1 4 7
2 2 2
2 5 5
1 3 4
1 2 3
1 7 7
2 1 1
1 8 8
2 5 5
2 3 7
1 1 4
2 2 7
2 7 8
2 2 6
1 7 8
1 1 4
1 1 5
1 1 6
2 6 7
2 8 8
1 7 7
2 2 5
1 8 8
1 4 5
1 5 6
2 5 5
1 5 5
2 6 8
1 4 6
1 8 8
1 3 6
1 4 4
1 1 1
1 6 7
2 1 6
1 6 6
2 8 8
2 2 8
2 1 3
1 1 7
2 7 7
1 3 4
2 5 6
2 3 8
2 4 7
2 4 4
2 4 8
1 8 8
1 3 7
1 1 8
2 6 6
2 4 8
2 2 8
1 3 4
2 8 8
2 1 7
1 1 4
2 3 6
1 3 5
2 6 6
1 7 8
2 4 6
2 1 8
2 5 7
2 2 7
2 4 4
1 7 7
1 5 5
2 5 7
1 6 7
2 6 7
1 2 2
2 1 3
1 3 6
2 4 8
2 6 8
1 1 8
1 6 6
2 5 5
2 5 8
1 8 8
2 7 8
2 6 8
2 5 7
1 1 8
1 5 8
2 5 7
2 4 6
1 6 6

1561880043
1782883760
2066665750
2331310501
985848817
1930426301
1101796919
3756951095
3893190544
1345461684
2331310501
460083124
584964617
1181287190
1032959559
720418976
264644751
584964617
584964617
3032223220
2283084109
3492306344
1441623042
2771887368
1305383593
2283084109
2547728860
3172771568
1345461684
721204066
720418976
2146844660
584964617
985848817
889687459
584964617
264644751
2066665750
1610891525
584964617
2070974649
721204066
528920484
1345461684
3036532119
625042708
721204066
4213510410
1253648359
3893190544
720418976
1181287190
1210007325
3753427286
2503302736
572876435
3224506802
584964617
2791393625
4478155161
625042708
3224506802
4213510410
1181287190
721204066
3756951095
2283084109
2311804244
1445931941
625042708
1305383593
1782883760
4478155161
1930426301
3492306344
572876435
720418976
264644751
1930426301
1345461684
1345461684
572876435
1253648359
2070974649
3224506802
2066665750
4478155161
625042708
584964617
2651630367
584964617
1441623042
2066665750
1930426301
4478155161
2195071052
1930426301
1782883760
625042708

说明

所有题目均为标准输入、标准输出；不需要文件读写。函数专题的函数签名是教学要求，普通 OJ 仅能依据程序输出来评测。