P16832 [HackerEarth] You are given a 1-indexed array A of the length N, and Q queries to answer.
提高
题目描述

You are given a 1-indexed array A of the length N, and Q queries to answer.

Each query consists of four integers L1, R1, L2 and R2.
Your task is to count the number of pairs of indices (i, j) satisfying the following conditions:
1) Ai = Aj
2) L1 ≤ i ≤ R1
3) L2 ≤ j ≤ R2

Input format
The first line contains one integer N.

The second line contains N space-separated integers A1, A2, ..., AN.

The third line contains one integer Q.

Each of the next Q lines contains four integers L1, R1, L2 and R2, describing one query.

Output format
For each query print the answer in a separate line.

Constraints
1 ≤ N, Q ≤ 50,000
1 ≤ Ai ≤ N
1 ≤ L1 ≤ R1 ≤ N
1 ≤ L2 ≤ R2 ≤ N

SAMPLE INPUT
7
1 5 2 1 7 2 2
8
1 3 4 5
2 3 5 7
1 4 3 7
2 6 4 7
1 6 2 5
3 3 6 7
4 5 1 4
2 3 4 5

SAMPLE OUTPUT
1
2
5
6
6
2
2
0

输入格式

见题面

输出格式

见题面

样例输入
20 17 1 17 17 5 5 17 1 1 5 17 17 14 14 1 5 14 1 1 17 20 15 15 1 14 5 15 1 5 16 19 16 16 4 10 8 15 15 19 4 16 2 5 5 11 10 10 7 7 5 15 10 11 3 6 4 18 4 6 12 14 2 17 3 11 6 6 2 14 7 18 1 10 2 19 13 15 2 13 1 18 7 15 3 7 13 20 4 18 3 8 3 4 12 13 4 18 5 17 11 14
样例输出
94 262 58 30 262 44 913 78 104 311 82 711 1002 791 19 1204 168 11 856 4 1437 462 448 117 123 2 9 41 6 79 132 117 58 179 459 502 219 584 430 569 164 0 188 1 8 229 42 1145 158 102 151 116 236 569 30 112 72 37 397 643 14 49 75 483 840 438 16 79 695 330 158 441 832 347 69 31 482 857 377 504 977 394 660 0 609 20 16 287 8 606 1597 76 13 0 177 1082 1 22 99 10 320 41 647 19 130 7 64 256 97 3 328 140 54 156 123 95 156 580 116 73 398 42 700 209 784 706 7 330 28 99 351 195 99 4 416 20 152 199 454 96 32 325 142 72 123 656 552 20 111 377 759 5 480 44 0 704 48 619 64 41 53 1032 710 175 87 33 512 37 16 210 1001 172 835 63 54 64 10 144 123 141 305 21 56 28 378 7 296 358 254 104 665 184 2 83 710 395 136 10 1011 76 419 86 11 313 3 92 737 83 435 108 319 0 102 175 98 88 585 1220 515 44 214 422 1120 51 355 213 45 53 682 46 454 586 80 120 113 37 457 117 20 1482 279 640 520 79 232 221 48 74 1455 725 14 6 52 76 8 162 1 71 408 61 609 551 16 709 151 88 226 538 77 10 344 36 147 1038 97 203 32 379 34 373 39 192 217 279 385 224 11 45 884 19 91 42 820 148 83 952 92 181 25 114 141 610 1079 19 74 126 155 88 718 6 287 524 18 497 2 464 61 16 431 53 120 110 392 13 124 46 1003 217 30 1 145 62 79 35 31 302 44 276 532 511 174 9 656 494 92 550 496 17 60 2 9 81 132 17 652 45 1032 195 77 66 770 19 896 20 252 7 486 1042 947 384 373 149 172 17 569 91 267 32 257 136 703 964 2 61 71 27 165 6 872 706 602 77 10 19 78 434 154 56 142 324 1035 954 678 209 2 278 404 1571 184 249 174 140 666 425 422 6 51 15 905 113 115 282 716 511 40 101 265 1519 77 5 3 119 739 460 805 663 55 939 1577 682 820 47 300 156 258 559 557 140 4 61 44 28 315 250 588 476 53 105 14 1 173 121 349 282 1010 39 292 83 49 1022 268 13 262 799 350 225 46 108 120 2 285 439 100 799 422 270 2 75 521 19 45 354 269 45 1559 813 35 51 695 8 6 108 358 114 106 380 714 265 703 734 97 79 14 67 680 248 205 193 44 802 346 411 292 33 482 1 617 11 304 887 71 128 258 280 62 62 591 199 1124 191 165 0 42 8 535 910 612 52 112 560 1119 153 384 221 186 32 267 8 255 10 15 39 1001 191 290 11 394 1092 140 213 620 96 1 636 124 372 44 59 936 10 1 77 68 389 29 314 336 10 135 137 99 195 3 130 486 141 33 46 340 289 56 248 0 1 526 520 101 28 89 11 573 42 464 208 964 12 1511 45 246 984 39 226 393 1415 6 75 516 691 1 913 792 25 22 26 232 547 44 560 5 51 6 22 386 336 108 121 0 39 452 84 954 133 2 252 37 96 89 87 24 195 22 2 20 352 73 250 285 767 673 148 165 20 471 7 57 1380 16 980 432 76 164 108 1159 161 96 118 353 196 15 680 413 366 1082 37 345 1718 335 365 0 30 53 179 3 0 9 0 215 144 242 439 296 61 178 85 514 54 59 108 211 204 531 560 26 974 116 399 83 210 752 159 31 230 2 130 1455 8 269 111 108 18 31 76 3 602 204 1232 7 410 0 197 1078 182 331 312 189 106 58 1036 421 270 1704 612 29 449 898 527 538 30 7 361 266 293 0 697 169 129 724 34 469 219 413 274 111 32 0 8 65 221 13 1496 126 1219 779 27 5 67 71 386 13 540 109 116 56 361 116 145 41 371 951 212 277 2 81 158 276 21 274 36 13 667 1151 43 522 19 244 61 242 178 936 59 186 21 110 273 30 453 637 758 44 75 1206 265 401 477 29 661 577 349 9 895 223 217 139 69 634 62 0 95 29 426 223 439 905 342 560 359 32 434 78 68 994 13 15 25 164 204 118 280 21 479 149 243 113 518 414 230 48 149 210 260 85 12 220 464 10 76 39 405 63 23 456 249 688 35 1452 488 118 10 447 456 442 49 159 319 2 91 8 420 535 17 23 275 149 4 289 633 349 16 583 343 367 22 2 45 17 196 78 350 912 273 113 185 388 267 60 153 58 99 80 1441 203 501 19 5 908 197 733 578 36 1204 264 144 1402 12 863 46 10 9 5 45 75 95 868 8 18 382 27 18 399 862 67 872 48 258 34 1184 15 501 175 14 359 322 3 739 211 1074 10 9 204 0