Trong giấc mơ, Thảo đang ở một hành tinh nào đó. Trước mặt Thảo là đám trẻ xếp thành một hàng, chìa tay sẵn sàng nhận kẹo từ anh ấy, anh ấy phải đảm bảo rằng mỗi đứa trẻ phải được nhận ít nhất 1 cây kẹo. Nếu có hai đứa trẻ đứng cạnh nhau nhưng độ tuổi khác nhau thì đứa lớn hơn phải được chia nhiều hơn. Vì xót thương cho cái hầu bao của mình nên muốn nhờ bạn tính toán làm sao mua ít kẹo nhất có thể nhưng vẫn chia đủ cho tất cả.

Đầu vào: Dòng đầu tiên chứa số nguyên N số lượng đứa trẻ Dòng tiếp theo chứa N số nguyên độ tuổi của mỗi đứa trẻ.

Đầu ra: Số kẹo ít nhất chia cho bọn trẻ.

Input

3
1 2 2

Output

4

Input

8
2 4 3 5 2 6 4 5

Output

12