Bessie và những người bạn đang chơi một phiên bản poker đặc biệt với một bộ bài có \(N\) (\(1 \le N \le 100\,000\)) hạng khác nhau, được đánh số thuận tiện từ \(1\) đến \(N\) (một bộ bài thông thường có \(N = 13\)). Trong trò chơi này, chỉ có một loại bộ bài mà những con bò có thể đánh: người chơi có thể chọn một lá bài mang số \(i\) và một lá bài mang số \(j\), rồi đánh một lá thuộc mỗi giá trị từ \(i\) đến \(j\). Loại bộ bài này được gọi là một "sảnh".

Trên tay Bessie hiện có \(a_i\) lá bài hạng \(i\) (\(0 \le a_i \le 100000\)). Hãy giúp cô tìm số sảnh ít nhất phải đánh để loại bỏ tất cả các lá bài của mình.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\).

Dòng thứ \(i+1\) trong \(N\) dòng tiếp theo chứa giá trị \(a_i\).

Dữ liệu ra

In ra số sảnh ít nhất Bessie phải đánh để loại bỏ tất cả các lá bài của mình.

Ví dụ

5
2
4
1
2
3

6

Nguồn

USACO 2013 March Contest, Silver — Problem 1: Poker Hands

Tác giả đề: Albert Gu, 2011.