433B.md (2262B)
1 Source: https://codeforces.com/problemset/problem/433/B 2 3 B. Kuriyama Mirai's Stones 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 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: 22 23 1. She will tell you two numbers, *l* and *r* (1 ≤ *l* ≤ *r* ≤ *n*), and you should tell her . 24 2. 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 . 25 26 For every question you should give the correct answer, or Kuriyama Mirai will say "fuyukai desu" and then become unhappy. 27 28 Input 29 30 The first line contains an integer *n* (1 ≤ *n* ≤ 105). The second line contains *n* integers: *v*1, *v*2, ..., *v**n* (1 ≤ *v**i* ≤ 109) — costs of the stones. 31 32 The third line contains an integer *m* (1 ≤ *m* ≤ 105) — 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. 33 34 Output 35 36 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. 37 38 Examples 39 40 Input 41 42 ``` 43 6 44 6 4 2 7 2 7 45 3 46 2 3 6 47 1 3 4 48 1 1 6 49 ``` 50 51 Output 52 53 ``` 54 24 55 9 56 28 57 ``` 58 59 Input 60 61 ``` 62 4 63 5 5 2 3 64 10 65 1 2 4 66 2 1 4 67 1 1 1 68 2 1 4 69 2 1 2 70 1 1 1 71 1 3 3 72 1 1 3 73 1 4 4 74 1 2 2 75 ``` 76 77 Output 78 79 ``` 80 10 81 15 82 5 83 15 84 5 85 5 86 2 87 12 88 3 89 5 90 ``` 91 92 Note 93 94 Please note that the answers to the questions may overflow 32-bit integer type.