Դասական նվեր

Արայիի ծննդյան օրվա կապակցությամբ նրան նվիրել են 1ից N թվերի A տեղափոխությունը (հաջորդականություն որում 1ից N թվերից յուրաքանչյուրը հանդիպում է ճիշտ մեկ անգամ)։ Նրա մոտ մի շատ բնական հարց առաջացավ. քանի՞ i, k, j ինդեքսներ կան այնպիսին, որ $i < k < j, A_i < A_j < A_k$: Արային շատ արագ գտավ այդ քանակը, իսկ դուք կկարողանա՞ք։

Մուտքային տվյալներ

Առաջին տողում տրված է մեկ բնական թիվ $N (1 ≤ N ≤ 200000)$։ Հաջորդ տողում տրված է N հատ ամբողջ թվեր՝ տեղափոխությունը։

Ելքային տվյալներ

Ելքում արտածեք մեկ թիվ պահանջվող քանակը։

Օրինակ

Բացատրություն

(i, k, j) եռյակներն են՝ (1, 3, 5), (2, 3, 4), (2, 3, 5), (2, 3, 7), (2, 4, 7), (2, 5, 7):

Ենթախնդիրներ

• Ենթախնդիր 0 (0 միավոր) Օրինակը,

• Ենթախնդիր 1 (5 միավոր) N ≤ 100,

• Ենթախնդիր 2 (25 միավոր) N ≤ 5000,

• Ենթախնդիր 3 (5 միավոր) N ≤ 200000, տեղափոխությունը կարելի է սորտավորել երկու իրար հարևան էլէմենտների տեղերը փոխելով,

• Ենթախնդիր 4 (15 միավոր) N ≤ 200000, տեղափոխությունը կարելի է սորտավորել երկու էլէմենտների տեղերը փոխելով,

• Ենթախնդիր 5 (50 միավոր) N ≤ 200000