Cho dãy số nguyên dương \(A_1,A_2,...,A_N\). Một bộ ba (\(i,j,k\)) được gọi là đẹp của dãy \(A\) đã cho nếu thỏa mãn:

• \(1 \le i \le j < k \le N\).
• Gọi dãy con liên tiếp \(A_i,A_{i+1},...,A_j\) là \(X\) và dãy con liên tiếp \(A_{j+1},A_{j+2},...,A_k\) là \(Y\) thì hai dãy này thỏa mãn:
  • Với mỗi giá trị xuất hiện trong dãy \(X\) thì cũng xuất hiện trong dãy \(Y\).
  • Với mỗi giá trị xuất hiện trong dãy \(Y\) thì cũng xuất hiện trong dãy \(X\).

Yêu cầu: Cho dãy số \(A\), hãy đếm số bộ ba đẹp (\(i,j,k\)) của dãy số này.

Input

• Dòng đầu chứa số nguyên \(N\) (\(1 \le N \le 2 \times 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(A_i\) (\(1 \le A_i \le N\)).

Output

• Ghi ra một số nguyên là số lượng bộ ba đẹp của dãy đã cho.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \le 500\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \le 5000\).
• Subtask \(3\) (\(20\%\) số điểm): \(A_i \le 50\).
• Subtask \(4\) (\(20\%\) số điểm): mỗi giá trị xuất hiện đúng hai lần.
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

7
3 1 2 1 2 3 1

4