Trước giờ học giáo dục thể chất, một lớp học 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 \leq p_{i} \leq 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 1 lần: Chọn 1 đoạn từ vị trí \(l\) đến \(r\ (1 \leq l \leq r \leq 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ấy 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\) \((i \leq i < j \leq 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 1 đ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 \leq i < j \leq n\).

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên dương \(n\ (2 \leq n \leq 3000)\)

+ Dòng thứ hai ghi lần lượt \(p\) số nguyên \(p_{1},p_{2},\ldots,p_{n}\) là chiều cao của từng học sinh trong hàng. Dữ liệu đảm bảo rằng tất cả các số \(p_{i}\) đều phân biệt.

Kết quả:

+ Ghi một số nguyên duy nhất cho biết kết quả bài toán.

Ví dụ:

Giải thích ví dụ:

Trong ví dụ đầu tiên, câu trả lời là tổng của các số sau: \(d(1,2) = 3\), \(d(1,3) = 4\), \(d(1,4) = 4\), \(d(1,5) = 4\), \(d(2,3) = 3\), \(d(2,4) = 3\), \(d(2,5) = 4\), \(d(3,4) = 3\), \(d(3,5) = 3\), \(d(4,5) = 4\). Ví dụ với hai học sinh ban đầu đứng ở vị trí 4 và 5, có chiều cao lần lượt là 1 và 3, thầy giáo có thể chọn đoạn với \(l = 1\) và \(r = 4\). Khi đó dãy học sinh sẽ thay đổi như sau: 5,2,4,1,3 \(\rightarrow\) 1,2,4,5,3 và khoảng cách giữa hai học sinh này là 4.

Ràng buộc:

+ Có 20% số test tương ứng 20% số điểm có \(n \leq 10\);

+ Có 20% số test khác tương ứng 20% số điểm có \(n \leq 50\);

+ Có 20% số test khác tương ứng 20% số điểm có \(n \leq 100\);

+ Có 20% số test khác tương ứng 20% số điểm có \(n \leq 600\);

+ Có 20% số test còn lại tương ứng 20% số điểm không có ràng buộc gì thêm.