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.awt.*;
import java.io.*;
import java.util.*;
import java.util.List;

public class Coding {

    static long MOD1 = 998244353;
    static long MOD = 1000000007;
    static long MOD2 = 1000000009;
    static long[] fact = new long[100002];
    static long[] pow2 = new long[100002];
    static int MAXVAL = 10000000;

    public static void main(String[] args) {
        BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        //precompute();
        try {
            int t = 1;
            while (t > 0) {
                String[] inputs = bi.readLine().split(" ");
                int n = Integer.valueOf(inputs[0].trim());
                inputs = bi.readLine().split(" ");
                int[] freq = new int[n + 1];
                int[] runn = new int[n + 1];
                for(int i=1;i<=n;++i) {
                    freq[i] = runn[i] = 0;
                }
                Point[] tritValues = new Point[n+1];
                int[] ar = new int[n];
                Map<Point, Integer> tritIndexes = new HashMap<>();
                tritValues[0] = new Point(0, 0);
                List<Integer> initial = new ArrayList<>();
                initial.add(-1);
                tritIndexes.put(new Point(0, 0), 1);
                long tritValue = 0;
                long tritValue1 = 0;
                int st = 0;
                long ans = 0;
                for(int i=0;i<n;++i) {
                    int val = Integer.parseInt(inputs[i].trim());
                    ar[i] = val;
                    //System.out.println(freq[ar[i]]);
                    tritValue = (tritValue - ((freq[ar[i]]%3) * modExp(3, ar[i], MOD))%MOD + 2*MOD)%MOD;
                    tritValue1 = (tritValue1 - ((freq[ar[i]]%3) * modExp(3, ar[i], MOD1))%MOD1 + 2*MOD1)%MOD1;
                   // System.out.println(tritValue + " " + tritValue1);
                    freq[ar[i]]++;
                    runn[ar[i]]++;
                    tritValue = (tritValue + ((freq[ar[i]]%3) * modExp(3, ar[i], MOD)))%MOD;
                    tritValue1 = (tritValue1 + ((freq[ar[i]]%3) * modExp(3, ar[i], MOD1)))%MOD1;
                    Point p = new Point((int) tritValue, (int) tritValue1);
                    //System.out.println(tritValue + " " + tritValue1);
                    if (runn[val] == 4) {
                        while (ar[st]!=val) {
                            runn[ar[st]]--;
                            int cur = tritIndexes.get(tritValues[st]);
                            tritIndexes.put(tritValues[st], cur-1);
                            st++;
                        }
                        runn[val]--;
                        int cur = tritIndexes.get(tritValues[st]);
                        tritIndexes.put(tritValues[st], cur-1);
                        st++;
                    }
                    int current = tritIndexes.getOrDefault(p, 0);
                    tritIndexes.put(p , current + 1);
                    tritValues[i+1] = p;
                    ans+=current;
                    //System.out.println(i + " " + st + " " + tritValue + " " + tritValue1 + " " + ans);
                }

                writer.append(ans + "\n");
                writer.flush();
                t--;
            }
            writer.flush();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }



    private static int gcd(int a, int b) {
        if (a<b) {
            return gcd(b, a);
        }
        if (a%b==0) {
            return b;
        }
        return gcd(b, a%b);
    }

    private static void dfs(int cur, List<Integer>[] adj, int[] nodeCount, int[] maxChild,  int parent, int[] par) {
        par[cur] = parent;
        for(int i=0;i<adj[cur].size();++i) {
            int nxt = adj[cur].get(i);
            if (nxt!=parent) {
                dfs(nxt, adj, nodeCount, maxChild, cur, par);
                nodeCount[cur]+=nodeCount[nxt];
                maxChild[cur] = Math.max(maxChild[cur], nodeCount[nxt]);
            }
        }
    }

    private static int findDist(int a, int b, int[] par) {
        Map<Integer, Integer> dist = new HashMap<>();
        int count = 0;
        dist.put(a, 0);
        while (par[a]!=-1) {
            a = par[a];
            count++;
            dist.put(a, count);
        }
        count=0;
        while(!dist.containsKey(b)) {
            b = par[b];
            count++;
        }
        return count+dist.get(b);
    }

    private static int findLongestPath(int cur, int prev, List<Integer>[] adj, int[] dep) {
        int diameter = 0;
        int highest = -1, second=-1;
        for(int i=0;i<adj[cur].size();++i) {
            int nxt = adj[cur].get(i);
            if (nxt!=prev) {
                diameter = Math.max(diameter, findLongestPath(nxt, cur, adj, dep));
                if (dep[nxt]>highest) {
                    second = highest;
                    highest = dep[nxt];
                } else if (dep[nxt]>second) {
                    second = dep[nxt];
                }
            }
        }
        diameter = Math.max(diameter, highest + second + 2);
        return diameter;
    }

    static long ncr(int n, int r) {
        long num = fact[n];
        long denom = (modExp(fact[r], MOD-2, MOD)*modExp(fact[n-r], MOD-2, MOD))%MOD;
        //System.out.println("num is " + num + " denom is" + denom);
        return (num*denom)%MOD;
    }

    static long modExp(long a, long b, long mod) {
        //System.out.println("a is " + a + " and b is " + b);
        if (a==1) return 1;
        long ans = 1;
        while (b!=0) {
            if (b%2==1) {
                ans = (ans*a)%mod;
            }
            a = (a*a)%mod;
            b/=2;
        }
        return ans;
    }

    private static void precompute() {
        fact[0] = 1;
        pow2[0] = 1;
        for(int i=1;i<=100000;++i) {
            fact[i] = (fact[i-1]*i)%MOD;
            pow2[i] = (pow2[i-1]*2)%MOD;
        }
    }
}