\(N\) chú bò của Nông dân John (\(N\le 3\times 10^5\)) có chiều cao \(1,2,\ldots,N\). Một ngày nọ, những chú bò đứng thành một hàng theo một thứ tự nào đó để chơi ném đĩa; gọi \(h_1\ldots h_N\) là chiều cao của những chú bò theo thứ tự này (do đó các \(h\) là một hoán vị của \(1\ldots N\)).

Hai chú bò ở vị trí \(i\) và \(j\) trong hàng có thể ném đĩa qua lại thành công khi và chỉ khi mọi chú bò nằm giữa chúng đều có chiều cao nhỏ hơn \(\min(h_i,h_j)\).

Hãy tính tổng khoảng cách giữa mọi cặp vị trí \(i<j\) có hai chú bò có thể ném đĩa qua lại thành công. Khoảng cách giữa vị trí \(i\) và \(j\) là \(j-i+1\).

Dữ liệu vào

Dòng đầu chứa một số nguyên \(N\). Dòng tiếp theo chứa \(h_1\ldots h_N\), cách nhau bởi dấu cách.

Dữ liệu ra

In tổng khoảng cách của mọi cặp vị trí có những chú bò có thể ném đĩa qua lại. Lưu ý rằng các số nguyên lớn trong bài có thể đòi hỏi kiểu số nguyên 64 bit (ví dụ long long trong C/C++).

Phân nhóm

• Các test 1–3 thỏa mãn \(N\le 5000\).
• Các test 4–11 không có ràng buộc bổ sung.

Ví dụ

7
4 3 1 2 5 6 7

24

Nguồn

USACO 2022 January Contest, Silver — Cow Frisbee: https://usaco.org/index.php?page=viewproblem2&cpid=1183

Tác giả: Quanquan Liu.