Farmer John đang xếp \(N\) con bò thành một hàng để chụp ảnh (\(1 \leq N \leq 100\,000\)). Chiều cao của con bò thứ \(i\) trong hàng là \(h_i\), và chiều cao của tất cả các con bò đều khác nhau.

Như với mọi bức ảnh chụp đàn bò, Farmer John muốn bức ảnh này trông đẹp nhất có thể. Ông cho rằng bò \(i\) trông "mất cân đối" nếu \(L_i\) và \(R_i\) chênh lệch nhau quá hệ số \(2\), trong đó \(L_i\) và \(R_i\) lần lượt là số bò cao hơn bò \(i\) nằm bên trái và bên phải nó. Nói cách khác, bò \(i\) mất cân đối nếu số lớn hơn trong hai số \(L_i\) và \(R_i\) lớn hơn nghiêm ngặt hai lần số nhỏ hơn. Farmer John hy vọng rằng không có quá nhiều bò bị mất cân đối.

Hãy giúp Farmer John tính tổng số bò bị mất cân đối.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). \(N\) dòng tiếp theo chứa \(h_1 \ldots h_N\), mỗi giá trị là một số nguyên không âm không quá \(1\,000\,000\,000\).

Dữ liệu ra

In số lượng bò bị mất cân đối.

Ví dụ

7
34
6
23
0
5
99
2

3

Nguồn

USACO 2017 January Contest, Gold — Balanced Photo. Tác giả đề: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=693