Các vương quốc của thế giới Bidibidi đã hoàn thành quá trình huấn luyện của họ. Bidibidi nhận ra bản thân đã làm cho thời gian trong mô hình đi quá nhanh không kịp quan sát, ông liền tinh chỉnh lại để thời gian trôi chậm hơn dễ quan sát. Khi mọi thứ bắt đầu sôi động hơn, Bidibidi quyết định nghỉ ngơi một xíu và xem các trận chiến cho zui. Có ~n~ vương quốc với sức mạnh tương ứng ~a_i~. Vương quốc có sức mạnh to lớn luôn muốn phô trương lực lượng của mình, vì thế vương quốc ~j~ sẽ tuyên chiến với vương quốc ~i~ và ~k~ cùng lúc nếu sức mạnh của cả hai vương quốc ấy đều thấp hơn nó (~i < j < k~). Bạn có biết nhà khoa học BIdibidi đã theo dõi tổng cộng bao nhiêu trận chiến không, hãy in ra kết quả nhé.

Input

Dòng đầy tiên là cặp giá trị ~n~.

Dòng thứ hai, gồm ~n~ giá trị ~a_i~.

Output

Một dòng duy nhất là số trận chiến mà Bidibidi theo dõi.

Constraints

~1 \le n \le 10^5~

~1 \le a_i \le 10^9~

Input Sample 1

4
1 3 5 2

Output Sample 1

3

Subtask

• SubTask ~1~: ~50~% số test ứng với ~n \le 500~.
• SubTask ~2~: ~40~% số test ứng với ~a_i \le n~.
• Subtask ~3~: ~10~% số test còn lại, không ràng buộc gì thêm.