Sonya và Robot

Cho một dãy $n$ số nguyên $a_1,a_2,\dots ,a_n$. Đặt hai con robot: một ở đầu trái (trước $a_1$) và một ở đầu phải (sau $a_n$). Ta gán cho robot trái một số $p$ và robot phải một số $q$ ($p$ và $q$ có thể bằng nhau).

Khi khởi động:

• Robot trái di chuyển sang phải, đọc lần lượt $a_1,a_2,\dots$ và dừng ở vị trí đầu tiên có giá trị bằng $p$.
• Robot phải di chuyển sang trái, đọc lần lượt $a_n,a_{n-1},\dots$ và dừng ở vị trí đầu tiên (tính từ phải) có giá trị bằng $q$.

Ta chỉ chọn các giá trị $p$, $q$ có xuất hiện trong dãy (nếu không robot sẽ đi tới đầu kia và va nhau). Cặp $(p,q)$ được gọi là hợp lệ nếu vị trí dừng của robot trái nằm thực sự bên trái vị trí dừng của robot phải (hai robot không gặp nhau).

Hai cặp $(p_1,q_1)$ và $(p_2,q_2)$ được coi là khác nhau nếu $p_1\ne p_2$ hoặc $q_1\ne q_2$.

Yêu cầu: đếm số cặp $(p,q)$ hợp lệ.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — độ dài dãy.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

• Một số nguyên duy nhất — số cặp $(p,q)$ hợp lệ.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le a_i\le {10}^5$

Ví dụ