Để chuẩn bị cho giải đấu hoofball sắp tới, bác nông dân John đang huấn luyện \(N\) cô bò của mình (được đánh số thuận tiện từ \(1 \dots N\), với \(1 \leq N \leq 100\)) cách chuyền bóng. Tất cả các cô bò đứng dọc theo một đường thẳng rất dài ở một phía của chuồng, trong đó cô bò \(i\) đứng cách chuồng \(x_i\) đơn vị (\(1 \leq x_i \leq 1000\)). Mỗi cô bò đứng tại một vị trí khác nhau.

Khi bắt đầu buổi tập, bác nông dân John sẽ chuyền một số quả bóng cho những cô bò khác nhau. Khi cô bò \(i\) nhận được bóng, dù từ bác nông dân John hay từ một cô bò khác, cô sẽ chuyền bóng cho cô bò gần mình nhất (nếu có nhiều cô bò cùng cách cô một khoảng bằng nhau, cô sẽ chuyền bóng cho cô bò nằm xa nhất về bên trái trong số đó). Để tất cả các cô bò đều được luyện chuyền bóng ít nhất một chút, bác nông dân John muốn bảo đảm rằng mỗi cô bò sẽ cầm bóng ít nhất một lần. Hãy giúp ông tìm số quả bóng ít nhất cần phát lúc đầu để điều này có thể xảy ra, giả sử ông trao bóng cho một tập hợp bò ban đầu thích hợp.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách, trong đó số nguyên thứ \(i\) là \(x_i\).

Dữ liệu ra

In ra số quả bóng ít nhất mà bác nông dân John phải chuyền ban đầu cho đàn bò để mỗi cô bò đều có thể cầm bóng ít nhất một lần.

Ví dụ

5
7 1 3 11 4

2

Nguồn

USACO 2018 February Contest, Bronze — Hoofball

Tác giả bài toán: Dhruv Rohatgi.