The Romans have attacked again. This time they are much more than the Persians but Shapur is ready to defeat them. He says: "A lion is never afraid of a hundred sheep". 

Nevertheless Shapur has to find weaknesses in the Roman army to defeat them. So he gives the army a weakness number.

In Shapur's opinion the weakness of an army is equal to the number of triplets *i*, *j*, *k* such that *i* &lt; *j* &lt; *k* and *a*<sub class="lower-index">*i*</sub> &gt; *a*<sub class="lower-index">*j*</sub> &gt; *a*<sub class="lower-index">*k*</sub> where *a*<sub class="lower-index">*x*</sub> is the power of man standing at position *x*. The Roman army has one special trait — powers of all the people in it are distinct.

Help Shapur find out how weak the Romans are.
The first line of input contains a single number *n* (3 ≤ *n* ≤ 10<sup class="upper-index">6</sup>) — the number of men in Roman army. Next line contains *n* different positive integers *a*<sub class="lower-index">*i*</sub> (1 ≤ *i* ≤ *n*, 1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>) — powers of men in the Roman army.
none
3
3 2 1
1
3
2 3 1
0
4
10 8 3 1
4
4
1 5 4 3
1
9
10 9 5 6 8 3 4 7 11
20
7
11 3 8 4 2 9 6
7
6
2 1 10 7 3 5
2
4
1 5 3 10
0
3
2 7 11
0
5
4 11 7 5 10
1
72
685 154 298 660 716 963 692 257 397 974 92 191 519 838 828 957 687 776 636 997 101 800 579 181 691 256 95 531 333 347 803 682 252 655 297 892 833 31 239 895 45 235 394 909 486 400 621 443 348 471 59 791 934 195 861 356 876 741 763 431 781 639 193 291 230 171 288 187 657 273 200 924
12140
20
840 477 436 149 554 528 671 67 630 382 805 329 781 980 237 589 743 451 633 24
185
59
996 800 927 637 393 741 650 524 863 789 517 467 408 442 988 701 528 215 490 764 282 990 991 244 70 510 36 151 193 378 102 818 384 621 349 476 658 985 465 366 807 32 430 814 945 733 382 751 380 136 405 585 494 862 598 425 421 90 72
7842
97
800 771 66 126 231 306 981 96 196 229 253 35 903 739 461 962 979 347 152 424 934 586 225 838 103 178 524 400 156 149 560 629 697 417 717 738 181 430 611 513 754 595 847 464 356 640 24 854 138 481 98 371 142 460 194 288 605 41 999 581 441 407 301 651 271 226 457 393 980 166 272 250 900 337 358 359 80 904 53 39 558 569 101 339 752 432 889 285 836 660 190 180 601 136 527 990 612
26086
45
955 94 204 615 69 519 960 791 977 603 294 391 662 364 139 222 748 742 540 567 230 830 558 959 329 169 854 503 423 210 832 87 990 44 7 777 138 898 845 733 570 476 113 233 630
2676
84
759 417 343 104 908 84 940 248 210 10 6 529 289 826 890 982 533 506 412 280 709 175 425 891 727 914 235 882 834 445 912 163 263 998 391 948 836 538 615 854 275 198 631 267 148 955 418 961 642 132 599 657 389 879 177 739 536 932 682 928 660 821 15 878 521 990 518 765 79 544 771 134 611 244 608 809 733 832 933 270 397 349 798 857
12571
32
915 740 482 592 394 648 919 705 443 418 719 315 916 287 289 743 319 270 269 668 203 119 20 224 847 500 949 910 164 468 965 846
1230
34
718 63 972 81 233 861 250 515 676 825 431 453 543 748 41 503 104 34 126 57 346 616 557 615 733 15 938 495 491 667 177 317 367 85
1202
73
874 34 111 922 71 426 229 972 557 232 144 590 170 210 792 616 890 798 983 797 488 8 859 538 736 319 82 966 474 513 721 860 493 375 81 69 662 444 766 451 571 94 365 833 720 703 826 270 437 542 147 800 146 173 564 160 928 57 732 774 292 250 716 131 949 1 216 456 53 322 403 195 460
13229
90
301 241 251 995 267 292 335 623 270 144 291 757 950 21 808 109 971 340 678 377 743 841 669 333 528 988 336 233 118 781 138 47 972 68 234 812 629 701 520 842 156 348 600 26 94 912 903 552 470 456 61 273 93 810 545 231 450 926 172 246 884 79 614 728 533 491 76 589 668 487 409 650 433 677 124 407 956 794 299 763 843 290 591 216 844 731 327 34 687 649
17239

def mergeSort(tp,low,high,count):
    if(low == high):
        return 
    mid = low + (high - low)//2
    mergeSort(tp,low,mid,count)
    mergeSort(tp,mid+1,high,count)
    merge(tp,low,mid+1,high,count)

def merge(tp,low,mid,high,count):
    
    temp = []
    
    index = 0
    small = 0 
    itr1,itr2 = low,mid
    while(itr1 < mid  and itr2 <= high):
        if(tp[itr1][0] < tp[itr2][0]):
            temp.append(tp[itr1])
            count[tp[itr1][1]] += small
            itr1 += 1
        else:
            temp.append(tp[itr2])
            small += 1
            itr2 += 1
        index += 1
    
    while(itr1 < mid):
        temp.append(tp[itr1])
        count[tp[itr1][1]] += small
        index += 1
        itr1 += 1
    
    while(itr2 <= high):
        temp.append(tp[itr2])
        index += 1
        itr2 += 1

    for index in range(low,high+1):
        tp[index] = temp[index-low]
    
    

n = int(input())
arr = list(map(int,input().split()))

count = [0 for index in range(n)]

tp = []
for index,value in enumerate(arr):
    tp.append((value,index))

mergeSort(tp,0,n-1,count)

sn = 0 
for val in count:
    sn += val*(val-1)//2
    
print(sn)