Nhân kỷ niệm \(50\) năm ngày thành lập trường, có \(N\) học sinh đăng ký tham gia trò chơi "những người bạn vui vẻ". \(N\) học sinh xếp thành một hàng đánh số từ \(1\) đến \(N\), người thứ \(i\) có số hiệu là bi.

Bạn có thể chọn một nhóm liên tiếp tối thiểu \(3\) học sinh để tham gia trò chơi. Nhóm được chọn cần thỏa mãn các điều kiện sau:

Chọn học sinh từ vị trí \(i\) đến vị trí \(j\) \((1 \le i \le j \le N\) và \(j - i \ge 2)\). Trong nhóm, phải có một học sinh làm lãnh đạo, sao cho số hiệu của học sinh này lớn hơn tất cả các số hiệu của những học sinh còn lại trong nhóm.

Yêu cầu

• Hãy tính xem có bao nhiêu cách chọn nhóm tham gia trò chơi. Hai cách chọn nhóm được xem là khác nhau nếu có số thành viên khác nhau hoặc lãnh đạo khác nhau.

Dữ liệu vào

• Dòng đầu tiên chứa số \(N (1 \le N \le 200.000)\).
• Dòng thứ hai chứa \(N\) số \(b_1, b_2, ..., b_N\) \((1 \le b_i \le N)\).

Dữ liệu ra

• Ghi một số duy nhất là số lượng cách chọn nhóm thỏa mãn điều kiện.

Input 1

7
1 2 3 4 3 2 5

Output 1

9

Giải thích 1

• Các nhóm được chọn tương ứng với các bộ lãnh đạo sau: (1,4,7), (2,3,4), (4,5,6), (5,7), (1,2,3), ...

Giới hạn

• Có 10% số điểm tương ứng với \(N \le 50\).
• Có 10% số điểm tương ứng với \(50 \le N \le 500\).
• Có 20% số điểm tương ứng với \(500 \le N \le 5000\).
• Có 60% số điểm còn lại tương ứng với các trường hợp khác.