Giờ học giáo dục thể chất

Trước giờ học giáo dục thể chất, một lớp gồm $n$ học sinh xếp thành một hàng. Tất cả học sinh trong lớp đều có chiều cao khác nhau. Vị trí thứ $i$ ($i = 1, 2, \ldots, n$) tính từ đầu bên trái của hàng là học sinh có chiều cao $p_i$ ($1 \le p_i \le n$).

Khi bắt đầu giờ học, thầy giáo có thể thay đổi thứ tự học sinh trong hàng. Để làm điều này, thầy giáo có thể thực hiện thao tác sau đúng một lần: chọn một đoạn từ vị trí $l$ đến vị trí $r$ ($1 \le l \le r \le n$) và sắp xếp các học sinh trong đoạn này theo chiều cao tăng dần từ trái sang phải. Ví dụ $n = 5$, ban đầu học sinh theo thứ tự có chiều cao là $5, 2, 4, 1, 3$ và thầy giáo chọn $l = 1$, $r = 4$ thì sau khi sắp xếp học sinh sẽ theo thứ tự có chiều cao là $1, 2, 4, 5, 3$.

Sử dụng thao tác này, thầy giáo có thể sắp xếp để hai học sinh nào đó cách xa nhau nhất có thể. Khoảng cách giữa hai học sinh bằng sự chênh lệch giữa các vị trí mà hai học sinh đứng. Với mỗi cặp học sinh, thầy giáo tính khoảng cách lớn nhất giữa hai học sinh này sau khi thực hiện đúng 1 thao tác nói trên. Bạn hãy giúp thầy giáo tìm tổng của các giá trị này.

Cụ thể hơn, hãy xét hai học sinh ban đầu ở vị trí $i$ và $j$ ($1 \le i < j \le n$). Gọi $d(i, j)$ là khoảng cách lớn nhất giữa hai học sinh đó mà thầy giáo có thể đạt được bằng cách chọn một đoạn và sắp xếp. Bạn cần tính tổng tất cả các giá trị $d(i, j)$ với mọi $i, j$ thỏa mãn $1 \le i < j \le n$.

Vào từ tệp văn bản phys.inp. Dòng đầu tiên chứa một số nguyên $n$ là số học sinh trong lớp ($2 \le n \le 3000$). Dòng thứ hai chứa $n$ số nguyên $p_1, p_2, \ldots, p_n$ là chiều cao của từng học sinh trong hàng ($1 \le p_i \le n$). Dữ liệu đảm bảo rằng tất cả các số $p_i$ đều phân biệt.

Ghi ra tệp văn bản phys.out một số nguyên là câu trả lời cho bài toán.

• Có 20% số test ứng với 20% số điểm thỏa mãn: $n \le 10$;
• 20% số test khác ứng với 20% số điểm thỏa mãn: $n \le 50$;
• 20% số test khác ứng với 20% số điểm thỏa mãn: $n \le 100$;
• 20% số test khác ứng với 20% số điểm thỏa mãn: $n \le 600$;
• 20% số test còn lại ứng với 20% số điểm: Không có thêm ràng buộc nào.