Cập nhật đoạn

Cho hai mảng ~a~ và ~b~ đều gồm ~n~ phần tử được đánh số từ ~1~ đến ~n~. Ban đầu ~a_i=0~ với mọi ~i~. Một thao tác cập nhật đoạn trên mảng ~a~ được thực hiện bằng cách chọn một số nguyên dương ~v~ và đoạn liên tiếp ~[l,r]~ ~(1 \le l \le r \le n)~, tiến hành cập nhật ~a_i = a_i+v~ với mọi ~l \le i \le r~.

Gọi ~m~ là số lần thực hiện thao tác để mảng ~a~ trở thành mảng ~b~. Hãy xác định giá trị nhỏ nhất của ~m~ sao cho khi xét bất kỳ hai đoạn trong số ~m~ đoạn đã lựa chọn, hai đoạn đó hoặc là không giao nhau, hoặc là một đoạn này bao phủ toàn bộ đoạn kia.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên ~b_i~ ~(0 \le b_i \le 10^9)~. Dữ liệu đảm bảo tồn tại ít nhất một chuỗi thao tác thỏa mãn.

Output

• In ra một số nguyên là giá trị nhỏ nhất của ~m~.

Samples

3
2 2 2

1

5
2 3 3 3 2

2

6
1 2 3 2 1 3

4

Scoring

• Subtask ~1~ với ~50\%~ số điểm: ~n \le 1000~
• Subtask ~2~ với ~50\%~ số điểm: Không còn ràng buộc gì thêm

Clarification

Trong ví dụ thứ hai, có thể chọn ~[l,r]=[1,5]~ và ~v=2~, sau đó chọn ~[l,r]=[2,4]~ và ~v=1~.