Vào thứ hai hàng tuần, trường THPT chuyên Lê Quý Đôn Đà Nẵng tổ chức lễ chào cờ, lớp của Flower_On_Stone Có \(N\) học sinh xếp thành một hàng dọc. Học sinh thứ \(i\) cao \(a_i\) cm.

Để một hàng dọc nhìn trở nên cân đối và đẹp hơn, Flower_On_Stone sẽ cho một vài học trò đứng lên các chiếc gạch sao cho người ở trước mặt mình sẽ không thấp hơn mình. Biết rằng mỗi chiếc gạch có chiều cao tùy ý Flower_On_Stone (chiều cao là một số nguyên và nó không âm).

Yêu cầu: Bạn hãy tính tổng chiếc gạch ít nhất có thể mà thỏa mãn điều kiện Flower_On_Stone đề ra.

Input

• Dòng đầu tiên chứa một số nguyên dương \(N\) \((1 \le N \le 10^6)\).
• Dòng tiếp theo chứa \(N\) số nguyên dương \(a_1,a_2,...,a_N\) \((1 \le a_i \le 10^9)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): Có \(N \le 5000\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
2 1 4 3 5

2