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
/**
 * BaZ :D
 */

import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class ACMIND
{
    static FastReader scan;
    static PrintWriter pw;
    static long MOD1 = 1000004249;
    static long MOD2 = 1000002667;
    static long INF = 2_000_000_000_000_000_000L;
    static long inf = 2_000_000_000;
    public static void main(String[] args) {
        new Thread(null,null,"BaZ",1<<27)
        {
            public void run()
            {
                try
                {
                    solve();
                }
                catch(Exception e)
                {
                    e.printStackTrace();
                    System.exit(1);
                }
            }
        }.start();
    }

    static void solve() throws IOException {
        scan = new FastReader();
        pw = new PrintWriter(System.out, true);
        StringBuilder sb = new StringBuilder();
        int n = ni();

        long pow[][] = new long[n+1][2];
        int P1 = 7, P2 = 31;
        pow[0][0] = pow[0][1] = 1;
        for(int i=1;i<=n;i++) {
            pow[i][0] = P1*pow[i-1][0];
            pow[i][0] %= MOD1;

            pow[i][1] = P2*pow[i-1][1];
            pow[i][1] %= MOD2;
        }

        int freq[] = new int[n+1];
        long h[][] = new long[n+1][2];
        int arr[] = new int[n+1];
        for(int i=1;i<=n;i++) {
            int x = ni();
            arr[i] = x;

            h[i][0] = h[i-1][0];
            h[i][0] -= (pow[x][0] * freq[x])%MOD1;
            h[i][0] += MOD1;
            h[i][0] %= MOD1;
            freq[x] = (freq[x] + 1) %3;
            h[i][0] += (pow[x][0] * freq[x])%MOD1;
            h[i][0] %= MOD1;

            h[i][1] = h[i-1][1];
            h[i][1] -= (pow[x][1] * freq[x])%MOD2;
            h[i][1] += MOD2;
            h[i][1] %= MOD2;
            freq[x] = (freq[x] + 1) %3;
            h[i][1] += (pow[x][1] * freq[x])%MOD2;
            h[i][1] %= MOD2;
        }

        //pa("hashes", h);

        TreeMap<Pair, Integer> map = new TreeMap<>();
        long ans = 0;
        int last[][] = new int[n+1][3];
        for(int i=0;i<=n;i++) {
            for(int j=0;j<3;j++) {
                last[i][j] = -1;
            }
        }


        int ptr = 0;
        add(map, new Pair((int)h[0][0], (int)h[0][1]));
        for(int i=1;i<=n;i++) {
            while (ptr<last[arr[i]][0]) {
                remove(map, new Pair((int)h[ptr][0], (int)h[ptr++][1]));
            }

//            pl("i: "+i+" Map: ");
//            for(int e: map.keySet()) {
//                p("{"+e +" " + map.get(e)+"}");
//            }
//            pl();

            Integer f = map.get(new Pair((int)h[i][0],(int)h[i][1]));
            if(f!=null) {
                ans+=f;
            }

            last[arr[i]][0] = last[arr[i]][1];
            last[arr[i]][1] = last[arr[i]][2];
            last[arr[i]][2] = i;

            add(map, new Pair((int)h[i][0],(int)h[i][1]));
        }

        pl(ans);
        pw.flush();
        pw.close();
    }

    static void add(TreeMap<Pair,Integer> map,Pair key)
    {
        Integer val = map.get(key);
        if(val==null)
            map.put(key,1);
        else map.put(key,val+1);
    }
    static void remove(TreeMap<Pair,Integer> map,Pair key)
    {
        Integer val = map.get(key);
        if(val==null)
            return;
        if(val==1)
            map.remove(key);
        else if(val>1)
            map.put(key, val-1);
    }

    static class Pair implements Comparable<Pair>
    {
        int x,y;
        Pair(int x,int y)
        {
            this.x=x;
            this.y=y;
        }
        public int compareTo(Pair other)
        {
            if(this.x!=other.x)
                return this.x-other.x;
            return this.y-other.y;
        }
        public String toString()
        {
            return "("+x+","+y+")";
        }
    }

    static int ni() throws IOException
    {
        return scan.nextInt();
    }
    static long nl() throws IOException
    {
        return scan.nextLong();
    }
    static double nd() throws IOException
    {
        return scan.nextDouble();
    }
    static void pl()
    {
        pw.println();
    }
    static void p(Object o)
    {
        pw.print(o+" ");
    }
    static void pl(Object o)
    {
        pw.println(o);
    }
    static void psb(StringBuilder sb)
    {
        pw.print(sb);
    }
    static void pa(String arrayName, Object arr[])
    {
        pl(arrayName+" : ");
        for(Object o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, int arr[])
    {
        pl(arrayName+" : ");
        for(int o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, long arr[])
    {
        pl(arrayName+" : ");
        for(long o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, double arr[])
    {
        pl(arrayName+" : ");
        for(double o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, char arr[])
    {
        pl(arrayName+" : ");
        for(char o : arr)
            p(o);
        pl();
    }
    static void pa(String listName, List list)
    {
        pl(listName+" : ");
        for(Object o : list)
            p(o);
        pl();
    }
    static void pa(String arrayName, Object[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(Object o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, int[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(int o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, long[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(long o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, char[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(char o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, double[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(double o : arr[i])
                p(o);
            pl();
        }
    }
    static class FastReader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public FastReader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public FastReader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[1000000];
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (c == '.') while ((c = read()) >= '0' && c <= '9') ret += (c - '0') / (div *= 10);
            if (neg) return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1) buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead) fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null) return;
            din.close();
        }
    }
}