Cho số nguyên dương \(N\) và dãy số nguyên không âm \(x_1,x_2,...,x_N\). Ban đầu tất cả các phần tử trong dãy \(x\) đều bằng \(0\).

Đức có thể dùng hai thao tác sau bao nhiêu lần tùy ý và theo bất kì thứ tự tùy ý:

• Thao tác \(1\): Cho một số nguyên dương \(k\) \((1 \le k \le N)\), tạo dãy số không giảm gồm \(k\) số nguyên không âm \(r_1,r_2,...,r_k\). Với mọi \(1 \le i \le k\) ta sẽ thay \(x_i\) bằng \(x_i + r_i\).
• Thao tác \(2\): Cho một số nguyên dương \(k\) \((1 \le k \le N)\), tạo dãy số không tăng gồm \(k\) số nguyên không âm \(r_1,r_2,...,r_k\). Với mọi \(1 \le i \le k\) ta sẽ thay \(x_{N-k+i}\) bằng \(x_{N-k+i} + r_i\).

Yêu cầu: Cho dãy số nguyên dương có \(N\) số nguyên dương \(a_1,a_2,...,a_N\) được nhập từ bàn phím. Bạn hãy tìm và in ra số lần thao tác ít nhất để dãy \(x\) trùng với dãy \(a\), biết rằng hai dãy \(x\) và \(a\) được gọi là trùng nhau khi với mọi \(1 \le i \le N\) thì \(x_i = a_i\).

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \((1 \le N \le 2 \times 10^5)\).
• Dòng tiếp theo chứa dãy số \(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\) (\(50\%\) số điểm): Có \(1 \le N \le 1000\) và các phần tử trong dãy \(a\) không quá \(5000\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
1 2 1 2 1

3