Co dãy

Bối cảnh

Cho dãy số nguyên \(a_1, a_2, \dots, a_n\ (0\leq a_i\leq 10^9, 1\leq n\leq 10^6)\). Với dãy số nguyên này ta có thể thực hiện xử lý \(Reduce(i)\) thay thế hai phần tử \(a_i\) và \(a_{i+1}\) bằng \(max(a_i, a_{i+1})\). Sau \(n - 1\) lần thực hiện phép xử lý trên, ta được dãy số có độ dài \(1\). Chi phí biến đổi dãy được tính bằng tổng chi phí của tất cả các phép xử lý đã thực hiện.

Yêu cầu

Yêu cầu: Cho \(n\) và các số \(a_i\). Hãy xác định chi phí nhỏ nhất đưa dãy về độ dài bằng \(1\).

Input

Dòng đầu tiên chứa số nguyên \(n\).

Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa số nguyên \(a_i\).

Output

Chi phí biến đổi tìm được.

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

3
1
2
3

Output

5

Giải thích ví dụ

• Ví dụ: n = 3, dãy số: 1, 2, 3
  • Giải thích: Tổng chi phí biến đổi là 1 + 2 + 3 = 6, nhưng vì chúng ta thay thế từng cặp với chi phí max, nên chi phí thực tế là 5.

Thông tin học tập

• Buổi: B04
• Concepts: loops, adjacent-pair minima/maxima, accumulation
• Giới hạn kiến thức: B01-B04
• Time limit: 1 second
• Memory limit: 20 MB
• Point: 30