609B - The Best Gift - CodeForces Solution

#include <bits/stdc++.h>

#define nour ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define ll long long
#define nn "\n"
using namespace std;
#define loop(i, n) for(int i=0;i<n;i++)
#define iff   if(f) cout<<"YES"<<nn; else cout<<"NO"<<nn;

ll lcm(ll a, ll b) {
    return (a * b) / __gcd(a, b);
}

ll smaller(ll y, vector<ll> &a, ll n) {
    ll l = 0;
    ll r = n;

    while (r > l) {
        ll m = (l + r) / 2;


        if (a[m] <= y) l = m + 1;
        else r = m;
    }
    return l;
} //upper_bound
ll greatere(ll x, int a[], int n) {
    ll l = 0;
    ll r = n;
    while (r > l) {
        int m = (l + r) / 2;
        if (a[m] >= x) r = m;
        else l = m + 1;
    }
    return r;
}  //lower_bound

int main() {
    nour

    ll n, m;
    cin >> n >> m;
    map<ll, ll> mp;
    vector<ll> v(n);
    ll x=n , sum=0;
    loop(i, n) {
        cin >> v[i];
        mp[v[i]]++;
    }
    for(int i=0;i<n;i++)
   {
        //    cout<<sum<<" "<<mp[v[i]]<<" "<<x<<nn;
        sum+= (x-1) - (mp[v[i]]-1);
        x--,mp[v[i]]--;
//        cout<<sum<<" "<<mp[v[i]]<<" "<<x<<nn;
    }
    cout<<sum;

}