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