Đếm số nghịch thế của phép thế

Submit solution
Points: 3
Time limit: 1.0s
Java 10 1.5s
Python 3 2.0s
Memory limit: 977M
Author:
TICHPX
Problem types
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Khi Kobe nghiên cứu toán học về Nhóm các phép thế, nhóm thay phiên, Kobe biết rằng nếu cho số nguyên dương n thì một phép thế là một hoán vị nào đó của tập \(\{1,2, 3,...,n\}\). Trên một phép thế nào đó người ta xác định cặp số mà số đứng trước lại lớn hơn số đứng sau gọi là một nghịch thế (Tức là \(1<=i<j<=n\) nhưng \(a[i]>a[j]\)). Bài toán đặt ra là cho một phép thế nào đó đếm số nghịch thế trên phép thế đó.

Input

Dòng đầu chứa số nguyên dương n là cỡ của phép thế \((1 <= n<= 10^5)\)

Dòng thứ 2 gồm n số nguyên dương là một dãy hoán vị nào đó của dãy \(\{1,2, 3,...,n\}\)

Output

Một số nguyên dương duy nhất là số nghịch thế đếm được của phép thế đã cho

Ví dụ 1

Input

5
4 5 1 3 2

Output

7

Giải thích : Có các cặp nghịch thế \(\{4,1\}, \{4,3\}, \{4,2\}, \{5,1\}, \{5,3\}, \{5,2\}, \{3,2\}\)

tichpx

Comments