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.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.util.Scanner;
import java.util.TreeMap;

public class Pashmak {
	static class Tools {

	    /** Taken from FastUtil implementation */

	    /** Return the least power of two greater than or equal to the specified value.
	   	 *
	   	 * <p>Note that this function will return 1 when the argument is 0.
	   	 *
	   	 * @param x a long integer smaller than or equal to 2<sup>62</sup>.
	   	 * @return the least power of two greater than or equal to the specified value.
	   	 */
	   	public static long nextPowerOfTwo( long x ) {
	   		if ( x == 0 ) return 1;
	   		x--;
	   		x |= x >> 1;
	   		x |= x >> 2;
	   		x |= x >> 4;
	   		x |= x >> 8;
	   		x |= x >> 16;
	   		return ( x | x >> 32 ) + 1;
	   	}

	    /** Returns the least power of two smaller than or equal to 2<sup>30</sup> and larger than or equal to <code>Math.ceil( expected / f )</code>.
	   	 *
	   	 * @param expected the expected number of elements in a hash table.
	   	 * @param f the load factor.
	   	 * @return the minimum possible size for a backing array.
	   	 * @throws IllegalArgumentException if the necessary size is larger than 2<sup>30</sup>.
	   	 */
	   	public static int arraySize( final int expected, final float f ) {
	   		final long s = Math.max( 2, nextPowerOfTwo( (long)Math.ceil( expected / f ) ) );
	   		if ( s > (1 << 30) ) throw new IllegalArgumentException( "Too large (" + expected + " expected elements with load factor " + f + ")" );
	   		return (int)s;
	   	}

	    //taken from FastUtil
	    private static final int INT_PHI = 0x9E3779B9;

	    public static int phiMix( final int x ) {
	   		final int h = x * INT_PHI;
	   		return h ^ (h >> 16);
	   	}


	}
	class IntIntMap4a  
	{
	    private static final int FREE_KEY = 0;

	    public static final int NO_VALUE = 0;

	    /** Keys and values */
	    private int[] m_data;

	    /** Do we have 'free' key in the map? */
	    private boolean m_hasFreeKey;
	    /** Value of 'free' key */
	    private int m_freeValue;

	    /** Fill factor, must be between (0 and 1) */
	    private final float m_fillFactor;
	    /** We will resize a map once it reaches this size */
	    private int m_threshold;
	    /** Current map size */
	    private int m_size;

	    /** Mask to calculate the original position */
	    private int m_mask;
	    private int m_mask2;

	    public IntIntMap4a( final int size, final float fillFactor )
	    {
	        if ( fillFactor <= 0 || fillFactor >= 1 )
	            throw new IllegalArgumentException( "FillFactor must be in (0, 1)" );
	        if ( size <= 0 )
	            throw new IllegalArgumentException( "Size must be positive!" );
	        final int capacity = Tools.arraySize(size, fillFactor);
	        m_mask = capacity - 1;
	        m_mask2 = capacity*2 - 1;
	        m_fillFactor = fillFactor;

	        m_data = new int[capacity * 2];
	        m_threshold = (int) (capacity * fillFactor);
	    }

	    public int get( final int key )
	    {
	        int ptr = ( Tools.phiMix( key ) & m_mask) << 1;

	        if ( key == FREE_KEY )
	            return m_hasFreeKey ? m_freeValue : NO_VALUE;

	        int k = m_data[ ptr ];

	        if ( k == FREE_KEY )
	            return NO_VALUE;  //end of chain already
	        if ( k == key ) //we check FREE prior to this call
	            return m_data[ ptr + 1 ];

	        while ( true )
	        {
	            ptr = (ptr + 2) & m_mask2; //that's next index
	            k = m_data[ ptr ];
	            if ( k == FREE_KEY )
	                return NO_VALUE;
	            if ( k == key )
	                return m_data[ ptr + 1 ];
	        }
	    }

	    public int put( final int key, final int value )
	    {
	        if ( key == FREE_KEY )
	        {
	            final int ret = m_freeValue;
	            if ( !m_hasFreeKey )
	                ++m_size;
	            m_hasFreeKey = true;
	            m_freeValue = value;
	            return ret;
	        }

	        int ptr = ( Tools.phiMix( key ) & m_mask) << 1;
	        int k = m_data[ptr];
	        if ( k == FREE_KEY ) //end of chain already
	        {
	            m_data[ ptr ] = key;
	            m_data[ ptr + 1 ] = value;
	            if ( m_size >= m_threshold )
	                rehash( m_data.length * 2 ); //size is set inside
	            else
	                ++m_size;
	            return NO_VALUE;
	        }
	        else if ( k == key ) //we check FREE prior to this call
	        {
	            final int ret = m_data[ ptr + 1 ];
	            m_data[ ptr + 1 ] = value;
	            return ret;
	        }

	        while ( true )
	        {
	            ptr = ( ptr + 2 ) & m_mask2; //that's next index calculation
	            k = m_data[ ptr ];
	            if ( k == FREE_KEY )
	            {
	                m_data[ ptr ] = key;
	                m_data[ ptr + 1 ] = value;
	                if ( m_size >= m_threshold )
	                    rehash( m_data.length * 2 ); //size is set inside
	                else
	                    ++m_size;
	                return NO_VALUE;
	            }
	            else if ( k == key )
	            {
	                final int ret = m_data[ ptr + 1 ];
	                m_data[ ptr + 1 ] = value;
	                return ret;
	            }
	        }
	    }

	    public int remove( final int key )
	    {
	        if ( key == FREE_KEY )
	        {
	            if ( !m_hasFreeKey )
	                return NO_VALUE;
	            m_hasFreeKey = false;
	            --m_size;
	            return m_freeValue; //value is not cleaned
	        }

	        int ptr = ( Tools.phiMix( key ) & m_mask) << 1;
	        int k = m_data[ ptr ];
	        if ( k == key ) //we check FREE prior to this call
	        {
	            final int res = m_data[ ptr + 1 ];
	            shiftKeys( ptr );
	            --m_size;
	            return res;
	        }
	        else if ( k == FREE_KEY )
	            return NO_VALUE;  //end of chain already
	        while ( true )
	        {
	            ptr = ( ptr + 2 ) & m_mask2; //that's next index calculation
	            k = m_data[ ptr ];
	            if ( k == key )
	            {
	                final int res = m_data[ ptr + 1 ];
	                shiftKeys( ptr );
	                --m_size;
	                return res;
	            }
	            else if ( k == FREE_KEY )
	                return NO_VALUE;
	        }
	    }

	    private int shiftKeys(int pos)
	    {
	        // Shift entries with the same hash.
	        int last, slot;
	        int k;
	        final int[] data = this.m_data;
	        while ( true )
	        {
	            pos = ((last = pos) + 2) & m_mask2;
	            while ( true )
	            {
	                if ((k = data[pos]) == FREE_KEY)
	                {
	                    data[last] = FREE_KEY;
	                    return last;
	                }
	                slot = ( Tools.phiMix( k ) & m_mask) << 1; //calculate the starting slot for the current key
	                if (last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos) break;
	                pos = (pos + 2) & m_mask2; //go to the next entry
	            }
	            data[last] = k;
	            data[last + 1] = data[pos + 1];
	        }
	    }


	    public int size()
	    {
	        return m_size;
	    }

	    private void rehash( final int newCapacity )
	    {
	        m_threshold = (int) (newCapacity/2 * m_fillFactor);
	        m_mask = newCapacity/2 - 1;
	        m_mask2 = newCapacity - 1;

	        final int oldCapacity = m_data.length;
	        final int[] oldData = m_data;

	        m_data = new int[ newCapacity ];
	        m_size = m_hasFreeKey ? 1 : 0;

	        for ( int i = 0; i < oldCapacity; i += 2 ) {
	            final int oldKey = oldData[ i ];
	            if( oldKey != FREE_KEY )
	                put( oldKey, oldData[ i + 1 ]);
	        }
	    }
	}
	class BinaryInd {
	    int MAX ;
	    int P[];
	    public BinaryInd(int size){
	        MAX=size;
	        P = new int[MAX+1];
	    }
	    public BinaryInd(){
	        this(1000000);
	    }
	    
	    public void add(int ind, int x){
	        while(ind<=MAX){
	            P[ind]+=x;
	            ind += ind & (-ind);
	        }
	    }
	    
	    public long getSum( int ind){
	        long res =0;
	        while(ind>0){
	            res += P[ind];
	            ind -= ind & (-ind);
	        }
	        return res;
	    }
	    /** inclusive **/
	    public long getSum(int a, int b){
	        return getSum(b) - getSum(a-1);
	    }
	    
	    public long get(int ind){
	        return getSum(ind)-getSum(ind-1);
	    }
	    
	    @Override
	    public String toString() {
	    	StringBuffer b = new StringBuffer();
	    	b.append("[");
	    	for(int i=0;i<=MAX;i++){
	    		b.append(i+ " = "+get(i)+" ");
	    	}
	    	b.append("]");
	    	return b.toString();
	    }
	}

	void solve(){
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[]A = new int[n];
		for(int i=0;i<A.length;i++)A[i]=scan.nextInt();
		System.out.println(doit(A));
	}
	
	long doitBrut(int[]A){
		long res =0;
		HashMap<Integer, Integer>Counts = new HashMap();
		int[]cc = new int[A.length];
		for(int i=cc.length-1;i>=0;i--){
			int ct = 0;
			if(Counts.containsKey(A[i]))ct = Counts.get(A[i]);
			cc[i]=++ct;
			Counts.put(A[i], ct);
		}
		Counts.clear();
		for(int i=0;i<A.length;i++){
			int ct = 0;
			if(Counts.containsKey(A[i]))ct = Counts.get(A[i]);
			cc[i]=++ct;
			Counts.put(A[i], ct);
			for(int j=i+1;j<A.length;j++){
				if(cc[j]<ct)res++;
			}

			
		}
		return res;
	}
	
	long doit(int[]A){
		long ts = System.currentTimeMillis();
		long res =0;
		IntIntMap4a Counts = new IntIntMap4a(A.length,0.8f);
		BinaryInd BI = new BinaryInd(A.length+1);
		System.err.println("Start");
		for(int i=A.length-1;i>=0;i--){
			int ct = 0;
			if(Counts.get(A[i])!=0)ct = Counts.get(A[i]);
			ct++;
			Counts.put(A[i], ct);
			BI.add(ct, 1);
		}
		System.err.println("done 1 ("+(System.currentTimeMillis()-ts)+")");
		IntIntMap4a CurCounts = new IntIntMap4a(A.length,0.8f);
		for(int i=0;i<A.length;i++){
			int ct = 0;
			if(CurCounts.get(A[i])!=0)ct = CurCounts.get(A[i]);
			ct++;
			CurCounts.put(A[i], ct);
			int backCnt = Counts.get(A[i]);
			BI.add(backCnt, -1);
			Counts.put(A[i], backCnt-1);
			res += BI.getSum(1,ct-1);
		}
		System.err.println("done 2 ("+(System.currentTimeMillis()-ts)+")");
		return res;
	}
public static void main(String[] args) {
	new Pashmak().solve();
//	System.out.println(new S459D().doit(new int[]{1, 2, 1, 1, 2, 2, 1}));
//	System.out.println(new S459D().doit(new int[]{1,1,1}));
//	System.out.println(new S459D().doit(new int[]{1, 2,3,4,5}));
//	int[]A = new int[1000000];
//	Random R = new Random();
//	for(int i=0;i<A.length;i++)A[i]=R.nextInt(1000000000);
//	System.out.println(new Pashmak().doit(A));
//	System.out.println(new S459D().doitBrut(A));
}
}
