Trong 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 đều có chiều cao khác nhau. Vị trí thứ i (i = 1, 2, ..., n) tính từ đầu bên trái của hàng là học sinh có chiều cao p_i (1 <= p_i <= 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 <= l <= r <= n) và sắp xếp các học sinh trong đoạn này tăng dần theo chiều cao từ trái qua phải.

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à 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 một thao tác trên. Bạn hãy giúp thầy giáo tìm tổng tất cả 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 <= i < j <= 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 <= i < j <= n.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên n là số học sinh trong lớp (2 <= n <= 3000).
Dòng thứ hai chứa n số nguyên p_1, p_2, ..., p_n là chiều cao của từng học sinh trong hàng (1 <= p_i <= n). 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 ra một số nguyên duy nhất là tổng các giá trị d(i, j) tìm được.

Ví dụ

5
5 2 4 1 3

35

Giải thích ví dụ

Trong ví dụ trên, tổng được tính từ các giá trị: d(1, 2) = 3, d(1, 3) = 4, d(1, 4) = 4, d(1, 5) = 5, d(2, 3) = 3, d(2, 4) = 3, d(2, 5) = 4, d(3, 4) = 4, d(3, 5) = 4, d(4, 5) = 1. Tổng cộng là 35.

Giới hạn

• 20% số điểm thỏa mãn: n <= 10
  
• 20% số điểm thỏa mãn: n <= 50
  
• 20% số điểm thỏa mãn: n <= 100
  
• 20% số điểm thỏa mãn: n <= 600
  
• 20% số điểm thỏa mãn: n <= 3000