ORDERED SET POLICY BASED DATA STRUCTURE

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ld long double
#define pb push_back
#define fe first
#define se second
#define st(x) sort(x.begin(),x.end())
#define rst(x) sort(x.rbegin(), x.rend())
#define all(x) x.begin(),x.end()
long double pi = 3.14159265358979323;

const double EPS = 1e-12;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
#define ordered_set tree < pair < ll , ll > ,null_type,less < pair < ll , ll > >,rb_tree_tag,tree_order_statistics_node_update >

//using policy based data structure

int main()
{
    fast;
    ll n;
    cin >> n ;
    ll a[n];
    ll l[n] , r[n];
    ordered_set s;
    map < ll , ll > mp;
    for(int i = 0 ; i < n ;i++ ){
        cin >> a[i];
        mp[a[i]]++;
        if(i < n - 1)
        l[i+1] = mp[a[i]];
    }
    mp.clear();
    /*for(int i = 1 ; i < n ;i++ ){
            cout << l[i] << " ";
    }*/
    for(int i = n - 1 ; i > 0 ;i-- ){
            mp[a[i]]++;
            r[n - i] = mp[a[i]];
    }
    ll l1[n];
    for(int i = 1 ; i < n  ;i++)
        l1[i] = l[n-i];
    ll ans = 0 ;

    for(int i = 1 ; i < n ; i++ )
    {
        s.insert({r[i],i});
    //Strickly less than
        ans += s.order_of_key({l1[i],-1});
    }
    cout << ans;























    return 0;

}