Để đảm bảo phủ sóng tốt trên các vùng dân cư thưa thớt dọc trục lộ giao thông người ta đặt một số trạm phát sóng. Các trạm này được lắp trên sân nóc một số nhà nằm gần mặt đường. Điều kiện để đặt 2 trạm tiếp sóng liên tiếp nhau là giữa 2 tòa nhà đó không có một nhà nào cao hơn hoặc bằng một trong hai nơi đặt trạm.

Trục lộ giao thông khá thẳng nên các nhà trên mặt đường có thể coi như nằm trên một đường thẳng. Từ đầu đến cuối đường có \(n\) nhà, nhà thứ \(i\) có độ cao \(h_i\).

Hãy xác định số cặp nhà có thể đặt trạm phát sóng. Dĩ nhiên, hai nhà liên tiếp nhau luôn thỏa mãn điều kiện đặt trạm.

Input

• Dữ liệu vào từ file văn bản BTS.INP:
  • Dòng đầu tiên chứa số nguyên \(n\) (\(2 \le n \le 2\cdot 10^6\));
  • Dòng thứ 2 chứa \(n\) số nguyên \(h_1, h_2, \dots, h_n\) (\(1 \le h_i \le 10^6\)).

Output

• Đưa ra file văn bản BTS.OUT một số nguyên là số cặp nhà có thể đặt trạm phát sóng.

Example

6
9 4 5 1 10 9

8

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 5000\).
• Subtask \(3\) (\(50\%\) số điểm): \(n \le 2\cdot 10^6\).