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à ~b_i~. Cần chọn một nhóm liên tiếp có ít nhất 3 học sinh, nghĩa là cần chọn một nhóm các học sinh từ vị trí ~i~ đến vị trí ~j~ sao cho ~1 \le i \le j \le N~ và ~j - i \ge 2~. Ban tổ chức sẽ đánh dấu 3 học sinh (bắt buộc có 1 học sinh ở đầu đoạn và 1 học sinh ở cuối đoạn) trong nhóm được chọn có vai trò lãnh đạo để tổ chức trò chơi cho nhóm mình. Để tránh nhầm lẫn, mỗi lãnh đạo phải có số hiệu khác với tất cả những người còn lại trong nhóm (làm lãnh đạo hoặc không).

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

• Dòng đầu tiên chứa số ~N~ (~1 \le N \le 2 \cdot 10^5~).
• Dòng thứ 2 chứa ~N~ số ~b_1, b_2, \dots, b_N~ (~1 \le b_i \le N~).

Kết quả

Chỉ một số duy nhất là số lượng cách tìm được.

Ví dụ

TroChoi.Inp

7
1 2 3 4 3 2 5

TroChoi.Out

9

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

Giới hạn

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