P15888 [HackerEarth] Lets uncomplicate the story.
普及
题目描述

Lets uncomplicate the story.

Given the N numbers (ai where 0 ≤ i < N), perform 3 kinds of queries:
Type 0 - Find the sum of frequencies of all numbers between X & Y inclusive.
Type 1 - Delete any one occurance of a number Z in array.
Type 2 - Insert the number Z in array.

Input Format

First line contains a single integer N - denoting the total number of numbers.

Second line contains N space-separated integers.

Third line contains a single integer Q - denoting the number of queries.

Q lines follow.

For every query of type 0, the query is of the form - 0 X Y - where 0 represents the query type and X,Y are the starting and ending numbers respectively.

For every query of type 1, the query is of the form 1 Z - where 1 represents the query type and Z is the number whose one occurance to be deleted.

For every query of type 2, the query is of the form 2 Z - where 2 represents the query type and Z is the number which is to be inserted anywhere in array.

Output format

Print the answer for every query of type 0 on a new line.

Constraints

1 ≤ N ≤ 10^6

0 ≤ ai ≤ 10^5

1 ≤ Q ≤ 10^6

SAMPLE INPUT
3
1 1 1
3
0 1 3
1 1
0 1 3

SAMPLE OUTPUT
3
2

输入格式

见题面

输出格式

见题面

样例输入
10 6 4 6 0 4 9 9 8 0 5 5 0 1 4 2 11 0 1 4 1 4 0 2 9
样例输出
299 167 442 54 327 78 434 112 96 134 185 128 101 155 401 72 75 117 243 172 365 432 19 91 30 181 338 467 327 25 9 208 98 225 37 53 250 71 201 226 570 343 302 61 35 36 46 376 34 71 226 302 293 16 30 355 152 418 170 364 396 84 74 168 177 184 155 457 13 338 408 307 178 188 99 81 355 50 163 379 71 278 67 268 17 447 106 182 85 184 86 19 109 192 10 40 5 326 168 62 473 217 6 152 131 300 316 10 128 124 21 36 80 174 38 5 31 141 138 289 221 391 215 120 2 140 117 241 16 16 156 19 144 109 9 120 38 195 174 267 262 41 12 19 54 51 330 370 625 117 290 28 5 367 281 79 264 219 40 138 216 162 95 36 191 340 32 228 98 19 284 258 65 79 398 206 36 56 82 197 51 210 314 505 94 13 107 49 122 152 367 288 4 366 50 100 11 389 494 28 59 148 144 122 182 62 42 193 106 395 286 82 237 154 110 253 69 31 309 140 457 9 551 58 111 134 193 31 223 435 15 54 565 214 41 31 120 57 526 419 297 384 103 3 416 4 89 90 17 398 17 181 553 494 59 143 223 672 182 105 196 119 256 4 263 157 305 503 357 166 61 140 342 1 51 115 19 81 33 65 79 7 352 199 26 40 155 43 18 323 303 133 293 219 109 408 52 14 482 81 105 71 134 268 663 29 20 33 5 443 223 653 148 48 79 698 313 357 102 213 30 604 332 149 6 632 249 137 327 661 571 136 361 45 152 228 46 17 137 451 40 156 84 158 240 514 67 50 160 267 111 61 610 136 211 202 246 226 503 390 63 186 124 7 73 104 120 572 108 159 23 33 420 291 411 151 215 155 192 79 120 25 80 51 207 177 70 507 497 98 18 86 44 627 168 206 358 154 157 58 365 405 249 253 102 17 403 44 452 248 60 109 19 204 585 102 361 1 77 211 95 248 168 31 532 141 44 249 144 379 154 56 79 306 525 77 21 72 166 11 121 394 103 401 20 139 321 193 38 16 392 191 290 136 21 424 34 104 470 65 137 337 5 249 75 64 240 281 226 34 140 350 386 110 60 94 172 171 25 10 231 81 282 201