Có ~N~ tòa nhà chọc trời ở Hà Nội, mỗi tòa nhà có chiều cao của tòa nhà thứ ~i~ là ~h_i~. Hôm nay, tiến sĩ Heinz Doofenshmirtz tự nhiên lại nổi hứng muốn chiếm thành phố Hà Nội, nên ông đã tạo cỗ máy động đất nhằm phá hủy các căn nhà ở đây. Cỗ máy đã bắn ~N-1~ căn nhà đầu tiên, chỉ còn tòa thứ ~N~ đang an toàn. Bạn là một đặc vụ của OWCA xuất phát từ tòa nhà thứ nhất, cần phải đến căn nhà thứ ~N~ để đảm bảo an toàn có thể thực hiện một cú nhảy từ tòa nhà thứ ~i~ đến tòa nhà thứ ~j~ (~i < j~) nếu thỏa mãn một trong các điều kiện sau:

• ~i + 1 = j~
• ~max(h_{i+1}, ..., h_{j-1}) < min(h_i, h_j)~
• ~max(h_i, h_j) < min(h_{i+1}, ..., h_{j-1})~

Hãy tính toán xem bạn cần ít nhất bao nhiêu bước nhảy để đảm bảo an toàn.

Input

Dòng đầu tiên chứa một số nguyên ~N~: số tòa nhà chọc trời ở Hà Nội

Dòng thứ hai chứa ~N~ số nguyên ~h_1, h_2,...,h_n~: chiều cao của tòa nhà thứ ~i~.

Output

In ra một số nguyên ~m~ là số lần nháy ít nhất mà bạn cần nhảy.

Giới hạn

~2 <= N <= 3*10^5~

~1 <= h_i <= 10^9~

Test mẫu

Input

5
1 3 1 4 5

Output

3