Để đả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~.

Yêu cầu

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.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa số nguyên ~n~ ~(2 \le n \le 2 \times 10^6)~.
• Dòng thứ hai chứa ~n~ số nguyên ~h_1, h_2, ..., h_n~ ~(1 \le h_i \le 10^6)~.

Dữ liệu đầu ra

Gồm một số nguyên là số cặp nhà có thể đặt trạm phát sóng.

Ràng buộc dữ liệu

• Subtask 1: 20% số test có ~n \le 100~.
• Subtask 2: 30% số test khác có ~n \le 5000~.
• Subtask 3: 50% số test còn lại có ~n \le 2 \times 10^6~.

Ví dụ

Ví dụ 1

INPUT

6
9 4 5 1 10 9

OUTPUT

8

Giải thích:

• Có ~6~ nhà nằm dọc theo trục lộ giao thông với độ cao lần lượt là: ~9, 4, 5, 1, 10, 9~.
• Có ~8~ cặp nhà có thể đặt trạm phát sóng là: ~(1, 2); (1, 3); (1, 5); (2, 3); (3, 4); (3, 5); (4, 5); (5, 6)~.