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
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
What do you think? What do you think?
1st on Billboard, what do you think of it
Next is a Grammy, what do you think of it
However you think, I’m sorry, but shit, I have no fcking interest
*******************************
I'm standing on top of my Monopoly board
That means I'm on top of my game and it don't stop
til my hip don't hop anymore
https://www.a2oj.com/Ladder16.html
*******************************
Shining through the city with a little funk and soul
*******************************
300iq as writer = Sad!
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class G
   {
      public static void main(String hi[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         int[] arr = new int[N+1];
         st = new StringTokenizer(infile.readLine());
         for(int i=0; i < N; i++)
            arr[i+1] = Integer.parseInt(st.nextToken());
         ArrayDeque<Integer>[] locs = new ArrayDeque[N+1];
         for(int i=1; i <= N; i++)
            locs[i] = new ArrayDeque<Integer>();
         int[] freq = new int[N+1];
         //do randomized solution
         long[] tags = new long[N+1];
         for(int i=1; i <= N; i++)
            tags[i] = (long)(Math.random()*Long.MAX_VALUE);
         HashMap<Long, Integer> map = new HashMap<Long, Integer>();
         long[] phash = new long[N+1];
         map.put(0L, 1);
         long curr = 0L;
         int dex = 0;
         long res = 0L;
         for(int i=1; i <= N; i++)
         {
            if(locs[arr[i]].size() == 3)
            {
               int left = locs[arr[i]].poll();
               while(dex < left)
                  pull(map, phash[dex++]);
            }
            locs[arr[i]].add(i);
            int delta = freq[arr[i]];
            freq[arr[i]]++;
            if(freq[arr[i]] == 3)
               freq[arr[i]] = 0;
            delta = freq[arr[i]]-delta;
            curr += delta*tags[arr[i]]*arr[i];
            if(map.containsKey(curr))
               res += map.get(curr);
            push(map, curr);
            phash[i] = curr;
         }
         System.out.println(res);
      }
      public static void push(HashMap<Long, Integer> map, long k)
      {
         if(!map.containsKey(k))
            map.put(k, 1);
         else
            map.put(k, map.get(k)+1);
      }
      public static void pull(HashMap<Long, Integer> map, long k)
      {
         int lol = map.get(k);
         if(lol == 1)
            map.remove(k);
         else
            map.put(k, lol-1);
      }
   }