Băng qua hẻm núi

Tại một hẻm núi cổ xưa có $n$ cột đá thẳng hàng, chiều cao của cột đá thứ $i$ là $h_i$. Một dòng dung nham đang dâng lên nhấn chìm $n - 1$ cột đá đầu tiên, vì vậy vị trí an toàn duy nhất lúc này là đỉnh của cột đá thứ $n$.

Một bước nhảy từ cột đá thứ $i$ sang cột đá thứ $j$ ($i < j$) được coi là hợp lệ nếu toàn bộ các cột đá nằm ở giữa đều thấp hơn hẳn hoặc cao hơn hẳn cả hai cột đá này. Cụ thể, bước nhảy là hợp lệ nếu $i < j$ và thỏa mãn ít nhất một trong ba đ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})$

Hiện tại, một nhà thám hiểm đang ở trên đỉnh cột đá thứ nhất và cần đến được đỉnh cột đá thứ $n$ với số bước nhảy hợp lệ ít nhất. Hãy giúp nhà thám hiểm tính toán số lượng bước nhảy tối thiểu này.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($2 ≤ n ≤ 3 · 10^5$), đại diện cho số lượng cột đá.

Dòng thứ hai chứa $n$ số nguyên $h_1, h_2, ..., h_n$ ($1 ≤ h_i ≤ 10^9$), trong đó $h_i$ là chiều cao của cột đá thứ $i$.

Kết quả

In ra một số nguyên duy nhất $k$, đại diện cho số bước nhảy hợp lệ ít nhất để đến được cột đá thứ $n$. Luôn tồn tại ít nhất một phương án di chuyển hợp lệ.

Chấm điểm

Subtask 1 (40 points). $n ≤ 3000$

Subtask 2 (60 points). $2 ≤ n ≤ 3 · 10^5$

Ví dụ

Input

5
1 3 1 4 5

Output

3

Ghi chú

Trong ví dụ trên, nhà thám hiểm có thể di chuyển theo lộ trình: $1 \to 2 \to 4 \to 5$ với tổng cộng $3$ bước nhảy.