Trung đang học Nhập môn lập trình về phần mảng 1 chiều và được thầy Tình giao cho một bài toán "đơn giản" như sau: cho một mảng số nguyên dương có ~n~ phần tử ~a_1, a_2, ..., a_n~ và các phần tử có giá trị không vượt quá ~n~. Đếm xem có bao nhiêu cặp chỉ số ~(L,R)~ với ~1 \le L < R \le n~ sao cho ~a_L \neq a_R~ và với mọi ~i~ mà ~L < i < R~ thì ~a_i~ cũng phải khác ~a_L, a_R.~

Với số ~n~ nhỏ, Trung có thể giải bài toán trong vòng một nốt nhạc. Tuy nhiên, thầy đã tăng độ khó lên bằng cách cho ~n~ rất lớn và thuật toán của Trung đòi hỏi chương trình chạy quá lâu. Hãy giúp Trung tìm cách tối ưu nhé.

Input:

Dòng đầu tiên gồm số nguyên dương ~n~ với ~2 \le n \le 2.10^5.~ Dòng tiếp theo gồm các phần tử là các số nguyên dương của mảng (các số không nhất thiết phân biệt).

Output:

Đáp số của bài toán.

Sample input:

4
3 1 4 2

Sample output:

6

Giải thích các cặp chỉ số ~(L,R)~ có thể là ~(1,2),(2,3),(3,4),(1,4),(1,3),(2,4)~. Vì tất cả các số hạng của dãy đều đôi một phân biệt nên cứ chọn bất kỳ cặp chỉ số nào cũng đều thỏa mãn.