Bitaro thích làm vườn. Hiện cậu đang trồng một loại cây gọi là cỏ Biba trong vườn nhà. Có \(N\) cây cỏ Biba được trồng thành một hàng từ tây sang đông, đánh số từ \(1\) đến \(N\) theo thứ tự đó. Hiện tại, chiều cao của cây thứ \(i\) (\(1 \le i \le N\)) là \(A_i\).

Nhờ được cải tiến giống, mỗi lần được tưới nước, một cây cỏ Biba sẽ cao thêm \(1\) đơn vị. Để khu vườn trông đẹp hơn, Bitaro muốn tưới nước một số lần sao cho điều kiện sau được thỏa mãn:

• Gọi \(B_i\) là chiều cao của cây thứ \(i\) sau khi hoàn thành tất cả các lần tưới. Phải tồn tại một số nguyên \(k\) (\(1 \le k \le N\)) sao cho \(B_j < B_{j+1}\) với mọi \(1 \le j \le k-1\), và \(B_j > B_{j+1}\) với mọi \(k \le j \le N-1\).

Tuy nhiên, Bitaro vụng về nên mỗi lần chỉ có thể tưới đồng thời tất cả các cây trong một đoạn liên tiếp. Cụ thể, trong một lần tưới, cậu chọn hai số nguyên \(L,R\) (\(1 \le L \le R \le N\)) rồi tưới các cây \(L,L+1,\ldots,R\).

Cho số lượng cây cỏ Biba và chiều cao hiện tại của chúng, hãy tìm số lần tưới ít nhất để thỏa mãn điều kiện trên.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn:

N
A_1 A_2 ... A_N

Tất cả các giá trị đầu vào đều là số nguyên.

Dữ liệu ra

In ra một dòng chứa số lần tưới ít nhất cần thực hiện.

Ràng buộc

• \(2 \le N \le 200\,000\).
• \(1 \le A_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).

Phân nhóm

• Nhóm 1 (40 điểm): \(N \le 2000\).
• Nhóm 2 (60 điểm): Không có ràng buộc bổ sung.

Ví dụ

5
3 2 2 3 1

3

5
9 7 5 3 1

0

2
2021 2021

1

8
12 2 34 85 4 91 29 85

93

Nguồn

JOI 2020/2021, vòng chung kết quốc gia, ngày 14/02/2021. Đề gốc của Ủy ban Olympic Tin học Nhật Bản: tiếng Anh, tiếng Nhật. Bản dịch theo giấy phép CC BY-SA 4.0.