You are given an array a consisting of n integers. We denote the subarray a[l..r] as the array [a_l, a_{l + 1}, ..., a_r] (1 ≤ l ≤ r ≤ n).

A subarray is considered good if every integer that occurs in this subarray occurs there exactly thrice. For example, the array [1, 2, 2, 2, 1, 1, 2, 2, 2] has three good subarrays:

  * a[1..6] = [1, 2, 2, 2, 1, 1]; 
  * a[2..4] = [2, 2, 2]; 
  * a[7..9] = [2, 2, 2]. 



Calculate the number of good subarrays of the given array a.

Input

The first line contains one integer n (1 ≤ n ≤ 5 ⋅ 10^5).

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ n).

Output

Print one integer — the number of good subarrays of the array a.

Examples

Input


9
1 2 2 2 1 1 2 2 2


Output


3


Input


10
1 2 3 4 1 2 3 1 2 3


Output


0


Input


12
1 2 3 4 3 4 2 1 3 4 2 1


Output


1
import java.io.*;
import java.util.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static BufferedReader br = new BufferedReader(new
            InputStreamReader(System.in));
    static PrintStream out = System.out;

    static void swap(double []A, int i, int j) {
        double s = A[i];
        A[i] = A[j];
        A[j] = s;
    }
    static void findK(double [] A, int l, int r, int k) {
        //System.out.println(l + " " + r);
        if (l == r) return;
        if (l == r - 1) {
            if (A[l] > A[r]) swap(A, l, r);
            return;
        }
        int j = l;
        int m = l + (r - l) / 2;
        if (A[m] >= A[l] && A[m] <= A[r]) swap(A,r,m);
        if (A[m] <= A[l] && A[m] >= A[r]) swap(A,r,m);
        if (A[l] >= A[m] && A[l] <= A[r]) swap(A,r,l);
        if (A[l] <= A[m] && A[l] >= A[r]) swap(A,r,l);
        boolean isOrdering = true;

        for (int i = l; i <= r; i++) {
            if (A[i] <= A[r]) {
                swap(A,i,j++);
            }
        }
        j--;
        if (j == k) return;
        double m1 = A[l];
        double m2 = A[r];
        for (int i = l; i <= k; i++) {
            m1 = Math.max(m1, A[i]);
        }
        for (int i = k + 1; i <= r; i++) {
            m2 = Math.min(m2, A[i]);
        }
        if (m1 <= m2) return;
        if (j > k) findK(A, l, j-1, k);
        if (j < k) findK(A, j + 1, r, k);
    }

    public static void main(String[] args) throws IOException {
        long MOD = 100000000;
        MOD = MOD * MOD * 100;
        int n = sc.nextInt();
        int []N = new int[n];
        long []H = new long[n];
        long []rand = new long[n + 1];
        Random random = new Random();
        rand[0] = random.nextInt() + 100;
        for (int i = 0; i < n; i++) {
            N[i] = sc.nextInt();
            while (rand[i+1] == 0)
                rand[i + 1] = Math.abs(random.nextLong()) % MOD;
        }
        long hash = 0;
        int []C = new int[n + 1];
        int []CC = new int[n + 1];
        int j = 0;
        long r = 0;
        Map<Long, Integer>map = new HashMap<>();
        map.put((long) 0, 1);
        for (int i = 0; i < n; i++) {
            int x = N[i];
            while (C[x] - CC[x] == 3) {
                CC[N[j]]++;
                //System.out.println("Deleting " + H[j]);
                if (j > 0)
                    map.put(H[j-1], map.get(H[j-1]) - 1);
                else
                    map.put((long) 0, map.get((long) 0) - 1);
                ++j;
            }
            hash = hash - (C[x] % 3) * rand[x];
            C[x]++;
            hash = hash + (C[x] % 3) * rand[x];
            hash = (hash % MOD);
            if (hash < 0) hash += MOD;
            H[i] = hash;
            int c = map.getOrDefault(hash, 0);
            r += c;
            //System.out.println("Insert " + hash + " : " + (c+1));
            map.put(hash, c + 1);
        }
        out.println(r);

    }


}