Cô giáo Alice muốn cho các con kẹo trong lớp mầm non. Các bạn nhỏ ngồi thành 1 hàng và mỗi bạn nhỏ sẽ có một điểm ưu tiên khi nhận kẹo. Cô Alice muốn đưa cho ít nhất mỗi bạn nhỏ 1 cái kẹo nhưng phải thỏa mãn điều kiện 2 bạn nhỏ ngồi gần nhau thì bạn nhỏ nào có điểm ưu tiên cao hơn sẽ được nhiều kẹo hơn. Cô Alice muốn giảm thiểu tối đa tổng số kẹo sẽ phát cho các bạn nhỏ.

Ví dụ mảng độ ưu tiên khi nhận kẹo của các bạn nhỏ như sau: [4, 6, 4, 5, 6, 2]

Cô Alice có thể phát kẹo theo phương án sau [1, 2, 1, 2, 3, 1]

Ràng buộc:

1 <= n <= 10^5

1 <= a[i] <= 10^5

Input 01:

6
4 6 4 5 6 2

Output 01:

10

Input 02:

8
1 2 8 9 6 5 4 3

Output 02:

21

Giải thích: Số kẹo sẽ chia như sau: 1 2 3 5 4 3 2 1