• Có \(n\) bãi cỏ được đánh số từ \(1\) đến \(n\) (từ trái sang phải). Và đám cỏ thứ \(i\) sẽ bị úa đi sau \(a_i\) ngày (cụ thể: ngày \(a_i\) cỏ vẫn chưa úa nhưng sang ngày \(a_{i+1}\) thì đã úa rồi).

• Hôm nay nhân dịp xuân Tân Sửu \(2021\). \(Kaninho\) dắt trâu ra bãi cỏ đó và anh ấy đã giao cho trâu một nhiệm vụ như sau:

• Nhiệm vụ của chú trâu phải đi từ bãi cỏ thứ nhất sang bãi cỏ thứ \(n\) trong nhiều ngày nhất có thể, biết rằng, trâu chỉ có thể đi từ trái sang phải và giả sử trâu đang ở bãi cỏ thứ \(i(1\le i<n-1)\) thì anh ấy có thể sang bãi cỏ \(i+1\) hoặc bãi có thứ \(i+2\) (tức là "bạn trâu" nhảy cóc), còn nếu trâu đang đứng ở bãi có thứ \(n-1\) thì anh ấy chỉ có thể sang bãi cỏ thứ \(n\) mà thôi. Và có một điều cần lưu ý đó là: Trâu không ăn cỏ úa, tức là nếu cỏ bị úa ở cánh đồng thứ nhất hoặc cánh đồng thứ \(n\) hoặc không tồn tại đường đi nào để đi từ cánh đồng \(1\) sang cánh đồng \(n\) thì xem như trâu chưa hoàn thành nhiệm vụ.

Yêu cầu: Cho một mảng gồm \(n\) phần tử \(a_i\) và xuất ra số ngày nhiều nhất trâu có thể hoàn thành nhiệm vụ.

Là một lập trình viên chuyên nghiệp, các bạn hãy giúp bạn trâu một tay nhé !

Input

• Dòng thứ nhất chứa số nguyên \(n(1\le n\le 1000)\) - Thể hiện số lượng bãi cỏ.

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n (1\le a_i\le 1000)\)

Output

• In ra đáp án cần tìm

Example

4
3 6 7 5

3