Quân đội yếu

Điểm: 6,00 (OI)

Giới hạn thời gian: 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho một dãy gồm $n$ số nguyên dương đôi một phân biệt $a_{1}, a_{2}, \dots, a_{n}$ — sức mạnh của các binh sĩ trong quân đội La Mã.

Định nghĩa độ yếu của quân đội là số bộ ba chỉ số $(i, j, k)$ thoả mãn:

$1 \leq i < j < k \leq n$ ,
$a_{i} > a_{j} > a_{k}$ .

Hãy tính độ yếu của quân đội La Mã.

Dữ liệu vào

Dòng đầu chứa một số nguyên $n$ — số binh sĩ.
Dòng thứ hai chứa $n$ số nguyên đôi một phân biệt $a_{1}, a_{2}, \dots, a_{n}$ — sức mạnh của từng binh sĩ theo thứ tự.

Dữ liệu ra

Một số nguyên duy nhất — độ yếu của quân đội.

Ràng buộc

$3 \leq n \leq 10^{6}$
$1 \leq a_{i} \leq 10^{9}$
Các giá trị $a_{i}$ đôi một phân biệt.
Kết quả có thể vượt phạm vi số nguyên 32 bit — hãy dùng kiểu 64 bit.

Ví dụ

Input	Output	Giải thích
3 3 2 1	1	Bộ ba $(1, 2, 3)$ thoả mãn $3 > 2 > 1$ .
3 2 3 1	0	Không có bộ ba nào giảm dần.
4 10 8 3 1	4	Tất cả $(\binom{4}{3}) = 4$ bộ ba đều giảm dần.
4 1 5 4 3	1	Chỉ có bộ ba $(2, 3, 4)$ tương ứng với $5 > 4 > 3$ .

Bình luận

Không có bình luận tại thời điểm này.