Những Bông Hoa

Submit solution
Points: 2
Time limit: 1.0s
Python 3 3.0s
Memory limit: 977M
Python 3 98M
Author:
TICHPX
Problem types
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Jonh rất thích hoa và cô ấy trồng được 1 hàng hoa ở trong vườn, mỗi bông hoa trong hàng cách nhau 20 cm.

Lão Marka là hàng xóm của Jonh, nhưng vì rất ghét Jonh nên lão ấy muốn phá hoại hàng hoa của Jonh. Vào mỗi buổi sáng Jonh sẽ bón phân bón cho bông hoa mà nó có chiều cao thấp nhất (trong trường hợp có nhiều cây thấp nhất bằng nhau thì sẽ chọn cây nằm ở bên trái nhất). Vào buổi chiều, Lão Marka sẽ tưới một loại thuốc làm chết cây hoa mà Jonh bón phân vào buổi sáng. Biết ảnh hưởng của thuốc diệt hoa là bán kính 20 cm (tức là tối đa có thể làm chết 3 cây).

Hỏi sau bao nhiêu ngày thì tất cả các cây hoa của Jonh đều bị chết, Bạn hãy lập trình tính số ngày này.

Input

Dòng đầu tiên chứa số lượng cây hoa N (1 ≤ N ≤ 10^5). Dòng thứ hai chứa N số nguyên a_i (1 ≤ a_i ≤ 10^5) - chiều cao của cây hoa (theo thứ tự chúng được trồng từ trái sang phải).

Output

In ra số ngày mà sau đó tất cả các cây hoa đều bị chết.

Ví dụ

Input

4
1 6 2 3

Output

2

Ví dụ 2

Input

5
8 6 2 9 2

Output

3
tichpx

Comments


  • 5
    TICHPX  commented on Oct. 12, 2018, 11:49 p.m.

    Thực ra thì pair đã có sẵn quan hệ thứ tự so sánh first trước và second sau


  • 1
    I_love_NguyenLinh  commented on Oct. 8, 2018, 5:14 a.m.

    dùng pair< int, int > sort luôn đc ko cần viết them hàm vì nó có hàm compare riêng r