Bakı şəhərində sıradan çıxmış binalar var. Bu binaların yerində yeni binalar tikiləcək. Bunun üçün mövcud binaların sökülməsi lazımdır.

Barış sıradan çıxmış binaların dağıdılması üzrə mütəxəssisdir. Onun belə binaları dağıdan super robotu var.

Şəhərdə n sayda yan-yana yerləşən bina var. Bu binaları dağıtmaq üçün Barış öz super robotunu işə saldı.

Binaların hər biri üst-üstə qoyulmuş müəyyən sayda blokdan ibarətdir. Robot bu binaların hamısını dağıtmalıdır. Bir gedişdə robot bütün daxili olmayan blokları dağıdır. Buna əsasən robotun bütün binaları neçə gedişə dağıdacağını tapın.

Bütün 4 tərəfində (sol, sağ, aşağı, yuxarı) dağılmamış blok və ya yer olan bloklar daxili bloklar sayılır (Müəyyənlik üçün şəklə baxın).

Giriş verilənləri

İlk sətirdə bir tam ədəd n (1 ≤ n ≤ 105) - ardıcıl binaların sayı, ikinci sətirdə isə boşluqla ayrılmış n sayda tam ədəd h1, h2, ... , hn (1 ≤ hi ≤ 109) - binaların hündürlükləri verilir.

Çıxış verilənləri

Çıxışa bir tam ədəd – bütün binaları dağıtmaq üçün lazım olan gedişlərin sayını verin.

Aşağıdakı şəkildə birinci nümunə üçün 3 mərhələ göstərilmişdir.