Cho dãy số nguyên ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^9; 2 \le n \le 10^6~). Hãy tính số dãy con gồm các số hạng liên tiếp ~a_i, a_{i+1}, ..., a_j~ sao cho trong dãy con này có ít nhất hai số hạng khác nhau.

Input Different.Inp

• Dòng 1 ghi số nguyên dương ~n~ (~2 \le n \le 10^6~).
• Dòng 2 ghi ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^9~).

Ouput Different.Out

Số đoạn con thỏa mãn.

Giới hạn

• Có 50% số test ứng với ~n \le 500~.
• Có 50% số test còn lại không có giới hạn gì thêm (~n \le 10^6~).

Ví dụ

Different.Inp

5
1 1 2 2 5

Different.Out

8

Giải thích Có 8 dãy con thỏa mãn (có chứa ít nhất 2 số khác nhau). Ví dụ: [1, 1, 2], [1, 2], [2, 5]...