Số bộ ba

Cho dãy số nguyên dương \(a_{1}, a_{2}, a_{3}, ..., a_{n}\). Một bộ ba \((i, j, k)\) được gọi là đẹp của dãy \(A\) đã cho nếu thoả mãn:

• \(1 ≤ i ≤ j < k ≤ 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 thoả 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 \((1 ≤ N ≤ 2 × 10^5)\).

• Dòng thứ hai chứa \(n\) số nguyên \(A_{i}\) \((1 ≤ A_{i} ≤ N)\).

Output

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

Example

7
3 1 2 1 2 3 1

4

Scoring

Subtask \(1\) (\(20\) điểm): \(N ≤ 500\).

Subtask \(2\) (\(20\) điểm): \(N ≤ 5000\).

Subtask \(3\) (\(20\) điểm): \(A_{i} ≤ 50\).

Subtask \(4\) (\(20\) điểm): Mỗi giá trị xuất hiện đúng hai lần.

Subtask \(5\) (\(20\) điểm): Không có ràng buộc gì thêm.