Tinky Winky tạo ra một dãy số gồm ~n~ số 0 bằng Tubbytronic Superdome rồi ra khỏi nhà để đi dạo với Dipsy. Khi trở về, Tinky Winky ngay lập tức nhận thấy dãy số đã bị thay đổi và Po đang đứng cười điên dại trong góc nhà.
Ôi! Po, chị đã làm gì - Tinky Winky sợ hãi hỏi
Tôi đã nâng cấp dãy số - Po đáp
Sau khi kiểm tra, Tinky Winky nhận ra Po đã thực hiện một số bước nâng cấp cho dãy số. Ở mỗi bước, Po lấy một đoạn bất kỳ và tăng tất cả các phần tử của đoạn đó lên cùng một giá trị nguyên dương. Ngoài ra, 2 đoạn bất kỳ đã được nâng cấp, hoặc là không giao nhau, hoặc là có một đoạn nằm hoàn toàn trong đoạn còn lại
Chị đã nâng cấp bao nhiêu lần thế, Po? - Laa-Laa (không biết từ đâu ra) hỏi.
Tôi thực sự không biết! Tôi chỉ biết là tôi đã thực hiện số bước nhỏ nhất để có thể tạo ra dãy số này - Po trả lời trong tuyệt vọng
Vậy chắc chắn phải là ~m~ rồi - Noo-Noo(cũng không biết từ đâu đến) khẳng định.
Hãy tìm số ~m~.
Input
Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 100000)~, độ dài của dãy số
Dòng thứ 2 gồm ~n~ số nguyên ~a_i~ ~(0 \le a_i \le 10^9)~, dãy số sau khi Po nâng cấp
Output
In ra số ~m~, số bước nâng cấp tối thiểu
Sample 1
Input
3
2 2 2
Output
1
Sample 2
Input
5
2 3 3 3 2
Output
2
Sample 3
Input
6
1 2 3 2 1 3
Output
4
Subtask
- ~5~ test đầu có ~n \le 1000~
- ~5~ test còn lại không có điều kiện gì thêm
Comments