Parmida is a clever girl and she wants to participate in Olympiads this year. Of course she wants her partner to be clever too (although he's not)! Parmida has prepared the following test problem for Pashmak.

There is a sequence a that consists of n integers a1, a2, ..., an. Let's denote f(l, r, x) the number of indices k such that: l ≤ k ≤ r and ak = x. His task is to calculate the number of pairs of indicies i, j (1 ≤ i < j ≤ n) such that f(1, i, ai) > f(j, n, aj).

Help Pashmak with the test.

Input

The first line of the input contains an integer n (1 ≤ n ≤ 106). The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109).

Output

Print a single integer — the answer to the problem.

Examples

Input

7
1 2 1 1 2 2 1


Output

8


Input

3
1 1 1


Output

1


Input

5
1 2 3 4 5


Output

0
		                                import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.Map;
import java.util.TreeSet;
		    
		    
		    
		                                                public class Solution1 implements Runnable
		                                                {
		                                                    static final long MAX = 464897L;
		                                                    static class InputReader
		                                                    {
		                                                        private InputStream stream;
		                                                        private byte[] buf = new byte[1024];
		                                                        private int curChar;
		                                                        private int numChars;
		                                                        private SpaceCharFilter filter;
		                                                        private BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		                                                 
		                                                        public InputReader(InputStream stream)
		                                                        {
		                                                            this.stream = stream;
		                                                        }
		                                                        
		                                                        public int read()
		                                                        {
		                                                            if (numChars==-1) 
		                                                                throw new InputMismatchException();
		                                                            
		                                                            if (curChar >= numChars)
		                                                            {
		                                                                curChar = 0;
		                                                                try 
		                                                                {
		                                                                    numChars = stream.read(buf);
		                                                                }
		                                                                catch (IOException e)
		                                                                {
		                                                                    throw new InputMismatchException();
		                                                                }
		                                                                
		                                                                if(numChars <= 0)                
		                                                                    return -1;
		                                                            }
		                                                            return buf[curChar++];
		                                                        }
		                                                     
		                                                        public String nextLine()
		                                                        {
		                                                            String str = "";
		                                                            try
		                                                            {
		                                                                str = br.readLine();
		                                                            }
		                                                            catch (IOException e)
		                                                            {
		                                                                e.printStackTrace();
		                                                            }
		                                                            return str;
		                                                        }
		                                                        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;
		                                                        }
		                                                        
		                                                        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 double nextDouble() 
		                                                        {
		                                                            int c = read();
		                                                            while (isSpaceChar(c))
		                                                                c = read();
		                                                            int sgn = 1;
		                                                            if (c == '-') 
		                                                            {
		                                                                sgn = -1;
		                                                                c = read();
		                                                            }
		                                                            double res = 0;
		                                                            while (!isSpaceChar(c) && c != '.') 
		                                                            {
		                                                                if (c == 'e' || c == 'E')
		                                                                    return res * Math.pow(10, nextInt());
		                                                                if (c < '0' || c > '9')
		                                                                    throw new InputMismatchException();
		                                                                res *= 10;
		                                                                res += c - '0';
		                                                                c = read();
		                                                            }
		                                                            if (c == '.') 
		                                                            {
		                                                                c = read();
		                                                                double m = 1;
		                                                                while (!isSpaceChar(c)) 
		                                                                {
		                                                                    if (c == 'e' || c == 'E')
		                                                                        return res * Math.pow(10, nextInt());
		                                                                    if (c < '0' || c > '9')
		                                                                        throw new InputMismatchException();
		                                                                    m /= 10;
		                                                                    res += (c - '0') * m;
		                                                                    c = read();
		                                                                }
		                                                            }
		                                                            return res * sgn;
		                                                        }
		                                                        
		                                                        public String readString() 
		                                                        {
		                                                            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 boolean isSpaceChar(int c) 
		                                                        {
		                                                            if (filter != null)
		                                                                return filter.isSpaceChar(c);
		                                                            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		                                                        }
		                                                     
		                                                        public String next() 
		                                                        {
		                                                            return readString();
		                                                        }
		                                                        
		                                                        public interface SpaceCharFilter 
		                                                        {
		                                                            public boolean isSpaceChar(int ch);
		                                                        }
		                                                    }
		                                                     
		                                                    public static void main(String args[]) throws Exception
		                                                    {
		                                                        new Thread(null, new Solution1(),"Solution",1<<26).start();
		                                                    }   
		                                                    static int gcd(int a, int b) 
		                                                    { 
		                                                      if (b == 0) 
		                                                        return a; 
		                                                      return gcd(b, a % b);  
		                                                    } 
		                                                    
		                                                    long MOD = 1000000007;
		                                                    
		                                                    TreeSet<Pair> adj[];
		                                                    ArrayList<Pair> adj2[];
		                                                    public void run() 
		                                                    {
		                                                        
		                                                            //InputReader sc= new InputReader(new FileInputStream("input.txt"));
		                                                            //PrintWriter w= new PrintWriter(new FileWriter("output.txt"));
		                                                            InputReader sc = new InputReader(System.in);
		                                                            PrintWriter w = new PrintWriter(System.out);
		                                                            int n = sc.nextInt();
		                                                            long[] arr = new long[n];
		                                                            for(int i = 0;i < n;i++) {
		                                                            	arr[i] = sc.nextLong();
		                                                            }
		                                                            Map<Long,Integer> tmap = new HashMap();
		                                                            long[] prefix=  new long[n];
		                                                            TreeSet<Long> tset = new TreeSet();
		                                                            for(int i = 0;i < n;i++) {
		                                                            	if(!tmap.containsKey(arr[i])) {
		                                                            		tmap.put(arr[i],1);
		                                                            	}else {
		                                                            		tmap.put(arr[i],tmap.get(arr[i]) + 1);
		                                                            	}
		                                                            	
		                                                            	prefix[i] = tmap.get(arr[i]);
		                                                            	tset.add(prefix[i]);
		                                                            }
		                                                            tmap.clear();
		                                                            suffix=  new long[n];
		                                                           
		                                                            for(int i = n-1;i >= 0;i--) {
		                                                            	if(!tmap.containsKey(arr[i])) {
		                                                            		tmap.put(arr[i],1);
		                                                            	}else {
		                                                            		tmap.put(arr[i],tmap.get(arr[i]) + 1);
		                                                            	}
		                                                            	
		                                                            	suffix[i] = tmap.get(arr[i]);
		                                                            	tset.add(suffix[i]);
		                                                            }
		                                                            tmap.clear();
		                                                            for(Long val: tset) {
		                                                            	tmap.put(val,tmap.size() + 1);
		                                                            }
		                                                            segTree = new long[8 * 1000005];
		                                                            long count = 0;
		                                                            for(int i = n-1;i > 0;i--) {
		                                                            	int ind = tmap.get(suffix[i]);
		                                                            	int ind2 = tmap.get(prefix[i-1]);
		                                                            	update(0, n-1, 0, ind, 1);
		                                                            	count += query(0, n-1, 0, 0, ind2-1);
		                                                            }
		                                                            w.println(count);
		                                                            w.close();
		                                                     }
		                                                    long[] suffix;
		                                                    long[] segTree;
		                                                    void update(int l,int r,int pos,int ind,int val) {
		                                                    	if(ind < l || ind > r) {
		                                                    		return;
		                                                    	}
		                                                    	if(l == r) {
		                                                    		segTree[pos] += val;
		                                                    		return;
		                                                    	}
		                                                    	int mid = (l + r)/2;
		                                                    	update(l, mid, 2*pos+1, ind, val);
		                                                    	update(mid+1, r, 2*pos+2, ind, val);
		                                                    	segTree[pos] = segTree[2*pos+1] + segTree[2*pos+2];
		                                                    }
		                                                    long query(int l,int r,int pos,int start,int end) {
		                                                    	if(l > r || l > end || r < start) {
		                                                    		return 0;
		                                                    	}
		                                                    	if(l >= start && r <= end) {
		                                                    		return segTree[pos];
		                                                    	}
		                                                    	int mid = (l + r)/2;
		                                                    	long p1 = query(l, mid, 2*pos+1, start, end);
		                                                    	long p2 = query(mid+1, r, 2*pos+2, start, end);
		                                                    	return (p1 + p2);
		                                                    }
		                                                    class Node implements Comparable<Node>{
		                                                    	int a;
		                                                    	int b;
		                                                    	long c;
		                                                    	Node(int a,int b,long c){
		                                                    		this.a = a;
		                                                    		this.b = b;
		                                                    		this.c = c;
		                                                    	}
		                                                    	public boolean equals(Object o) {
		                                                    		Node p = (Node)o;
		                                                            return this.a == p.a && this.b == p.b && this.c == p.c;
		                                                        }
		                                                    	public int compareTo(Node n) {
		                                                    		if(n.c == this.c) {
		                                                    			if(n.a == this.a) {
		                                                    				return Integer.compare(this.b,n.b);
		                                                    			}
		                                                    			return Integer.compare(this.a,n.a);
		                                                    		}
		                                                    		return Long.compare(this.c,n.c);
		                                                    	}
		                                                    	public int hashCode(){
		                                                            return Long.hashCode(a)*27 + Long.hashCode(b)* 31 + Long.hashCode(c) * 3;
		                                                        }
		                                                    }
		                                                    class Pair implements Comparable<Pair>{
		                                                        long a;
		                                                        int b;
		                                                        //int c;
		                                                        Pair(long a,int b){
		                                                            this.b = b;
		                                                            this.a = a;
		                                                        }
		                                                        public boolean equals(Object o) {
		                                                            Pair p = (Pair)o;
		                                                            return this.a == p.a && this.b == p.b;
		                                                        }
		                                                        public int hashCode(){
		                                                            return Long.hashCode(a)*27 + Long.hashCode(b)* 31;
		                                                        }
		                                                        public int compareTo(Pair p) {
		                                                            return Long.compare(this.a,p.a);
		                                                        }
		                                                    }
		                                    }