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 Solution extends PrintWriter {
    

    private void solve() {
        n = sc.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int[] c = new int[n+1];
        int[][] pos = new int[n+1][3];
        for(int i = 0; i <= n; i++) Arrays.fill(pos[i], n);
        int[][] f = new int[n][];
        for(int i = n-1; i >= 0; i--) {
            pos[a[i]][c[a[i]]++] = i;
            if(c[a[i]] >= 3) c[a[i]]-=3;
            
            int t = c[a[i]]-3;
            if(t < 0) t += 3;

            f[i] = new int[] {i, pos[a[i]][t], 0};            
        }
        Arrays.sort(f, Comparator.comparing(arr -> arr[1]));
        for(int i = 0; i < n; i++) {
            f[i][2] = i;
        }
        Arrays.sort(f, Comparator.comparing(arr -> arr[0]));
        min = new int[4*n];
        cnt = new int[4*n];
        add = new int[4*n];
        old = new boolean[4*n];
        build(0, n-1, 1);
        bit = new int[n];
        HashMap<Integer, Integer> map = new HashMap<>();
        long ans = 0L;
        for(int i = n-1; i >= 0; i--) {
            //shift segtree
            add_range(0, n-1, 1, 0, n-1, +1);
            if(f[i][1] < n) {
                
                Integer del = map.get(a[i]);
                Integer ins = f[i][2];
                if(del != null) {
                    //remove from segtree
                    set_point(del, INF);
                    add_range(0, n-1, 1, del+1, n-1, +3);
                    
                    //remove from bit
                    add(del, -1);
                }
                //update map
                map.put(a[i],ins);
                
                //add to bit
                int idx = query(ins) + 1;                
                add(ins, 1);
                
                //add to segtree
                set_point(ins, f[i][1]-i+1 - 3*idx);
                add_range(0, n-1, 1, ins+1, n-1, -3);

                int[] q = query(0,n-1,1,0,n-1);
                if(q[0] == 0) ans += q[1];
            }
        }
        println(ans);
    }
    
    int INF = 1<<22;
    
    int n;
    
    int[] min;
    int[] cnt;

    int[] add;
    boolean[] old;
    
    void build(int il, int ir, int i) {
        min[i] = INF;
        cnt[i] = ir-il+1;
        if(il != ir) {
            int imid = (il+ir)/2;
            build(il, imid, 2*i);
            build(imid+1, ir, 2*i+1);
        }
    }
    
    int[] query(int il, int ir, int i, int ql, int qr) {
        if(il > qr || ir < ql) return new int[] {INF, -1};

        lazy_propagate(il, ir, i);
        
        if(ql <= il && ir <= qr) {
            return new int[] {min[i], cnt[i]};
        }
        
        int imid = (il + ir) / 2;
        int[] l = query(il, imid, 2*i, ql, qr);
        int[] r = query(imid+1, ir, 2*i+1, ql, qr);
        if(l[0] < r[0]) return l;
        else if(r[0] < l[0]) return r;
        else return new int[] {l[0], l[1]+r[1]};
    }
    
    void set_point(int q, int val) {
        add_range(0, n-1, 1, q, q, val-query(0, n-1, 1, q, q)[0]);
    }
    
    void add_range(int il, int ir, int i, int ql, int qr, int val) {
        lazy_propagate(il, ir, i);
        if(il > qr || ir < ql) return;
        
        if(ql <= il && ir <= qr) {
            push(i, val);
            lazy_propagate(il, ir, i);
            return;
        }
        
        int imid = (il + ir) / 2;
        add_range(il, imid, 2*i, ql, qr, val);
        add_range(imid+1, ir, 2*i+1, ql, qr, val);
        if(min[2*i] < min[2*i+1]) {
            min[i] = min[2*i];
            cnt[i] = cnt[2*i];
        } else if(min[2*i+1] < min[2*i]) {
            min[i] = min[2*i+1];
            cnt[i] = cnt[2*i+1];
        } else {
            min[i] = min[2*i];
            cnt[i] = cnt[2*i]+cnt[2*i+1];
        }
    }
    
    void push(int i, int val) {
        old[i] = true;
        add[i] += val;
    }
    
    void lazy_propagate(int il, int ir, int i) {
        if(old[i]) {
            min[i] += add[i];
            if(min[i] > INF) min[i] = INF;
            if(il != ir) {
                push(2*i, add[i]);
                push(2*i+1, add[i]);
            }
            lazy_reset(i);
        }
    }
    
    void lazy_reset(int i) {
        add[i] = 0;
        old[i] = false;
    }
    
    int[] bit;
    
    int query(int i) {
        int sum = 0;
        while(i >= 0) {
            sum += bit[i];
            i = (i & (i+1)) - 1;
        }
        return sum;
    }
    
    void add(int i, int x) {
        while(i < n) {
            bit[i] += x;
            i = i | (i+1);
        }
    }
    

//  Solution() throws FileNotFoundException { super(new File("output.txt")); }
//  InputReader sc = new InputReader(new FileInputStream("test_input.txt"));
  Solution() { super(System.out); }
  InputReader sc = new InputReader(System.in);
  static class InputReader {
      InputReader(InputStream in) { this.in = in; } InputStream in;
      
      private byte[] buf = new byte[16384];
      private int    curChar;
      private int    numChars;
      
 
      public int read() {
          if (numChars == -1)
              throw new InputMismatchException();
          if (curChar >= numChars) {
              curChar = 0;
              try {
                  numChars = in.read(buf);
              } catch (IOException e) {
                  throw new InputMismatchException();
              }
              if (numChars <= 0)
                  return -1;
          }
          return buf[curChar++];
      }
 
      public String nextLine() {
          int c = read();
          while (isSpaceChar(c))
              c = read();
          StringBuilder res = new StringBuilder();
          do {
              res.appendCodePoint(c);
              c = read();
          } while (!isEndOfLine(c));
          return res.toString();
      }
 
      public String nextString() {
          int c = read();
          while (isSpaceChar(c))
              c = read();
          StringBuilder res = new StringBuilder();
          do {
              res.appendCodePoint(c);
              c = read();
          } while (!isSpaceChar(c));
          return res.toString();
      }
 
      public long nextLong() {
          int c = read();
          while (isSpaceChar(c))
              c = read();
          int sgn = 1;
          if (c == '-') {
              sgn = -1;
              c = read();
          }
          long res = 0;
          do {
              if (c < '0' || c > '9')
                  throw new InputMismatchException();
              res *= 10;
              res += c - '0';
              c = read();
          } while (!isSpaceChar(c));
          return res * sgn;
      }
 
      public int nextInt() {
          int c = read();
          while (isSpaceChar(c))
              c = read();
          int sgn = 1;
          if (c == '-') {
              sgn = -1;
              c = read();
          }
          int res = 0;
          do {
              if (c < '0' || c > '9')
                  throw new InputMismatchException();
              res *= 10;
              res += c - '0';
              c = read();
          } while (!isSpaceChar(c));
          return res * sgn;
      }
 
      private boolean isSpaceChar(int c) {
          return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
      }
 
      private boolean isEndOfLine(int c) {
          return c == '\n' || c == '\r' || c == -1;
      }
  }
 
    public static void main(String[] $) {
        new Thread(null, new Runnable() {
            public void run() {
                long start = System.nanoTime();
                try {Solution solution = new Solution(); solution.solve(); solution.flush();} 
                catch (Exception e) {e.printStackTrace(); System.exit(1);}
                System.err.println((System.nanoTime()-start)/1E9);
            }
        }, "1", 1 << 27).start();
 
    }
    

}