#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define el '\n'
#define FIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned uint;
typedef __int128 bint;
typedef long double ld;
typedef complex<ld> pt;
typedef unsigned long long ull;

template<typename T, typename X>
using hashTable = gp_hash_table<T, X>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

// mt19937_64 for unsigned long long
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());

ll doWork(vector<int> v)
{
    int n = v.size();


//    int n;
//    cin >> n;
//    vector<int> v(n);
    vector<ll> suff(n + 1);
    ordered_set<int> a, b;

//    for(int i = 0; i < n; i++)
//        cin >> v[i];


    for(int i = n - 1; i >= 0; i--)
    {
        suff[i] = b.size() - b.order_of_key(v[i]), b.insert(v[i]);
        if(i + 1 < n)
            suff[i] += suff[i + 1];
    }

    ll ans = suff[0], invA = 0;
    for(int i = 0; i < n; i++)
    {
        invA += a.size() - a.order_of_key(v[i]);
        cout << invA << ' ';
        a.insert(v[i]);
        if(i + 1 < n)
            ans = min(ans, invA + suff[i + 1]);
        else
            ans = min(ans, invA);
    }
    cout << '\n';
    for(int i = 0; i < n; i++)
        cout << suff[i] - suff[i + 1] << ' ';
    exit(0);
    return ans;
}

ll doWork2(vector<int> &v)
{
    int n = v.size();


//    int n;
//    cin >> n;
//    vector<int> v(n);
    vector<ll> suff(n);
    ordered_set<int> a, b;

//    for(int i = 0; i < n; i++)
//        cin >> v[i];


    for(int i = n - 1; i >= 0; i--)
    {
        suff[i] = b.size() - b.order_of_key(v[i]), b.insert(v[i]);
//        if(i + 1 < n)
//            suff[i] += suff[i + 1];
    }

    ll ans = 0, invA = 0;
    for(int i = 0; i < n; i++)
    {
        invA = a.size() - a.order_of_key(v[i]);
        a.insert(v[i]);
        ans += min(invA, suff[i]);
//        if(i + 1 < n)
//            ans += min(invA, suff[i + 1]);
    }

    return ans;
}

bool valid(vector<int> &v)
{
    bool desc = false;
    for(int i = 1; i < v.size(); i++)
    {
        if(v[i - 1] < v[i])
        {
            if(!desc)
                continue;
            else
                return false;
        }
        else
        {
            if(desc)
                continue;
            else
                desc = 1;
        }
    }
    return true;
}

ll dist(vector<int> a, vector<int> &b)
{
    int ret = 0;
    for(int i = 0; i < a.size(); i++)
    {
        int j = find(a.begin(), a.end(), b[i]) - a.begin();
        if(i == j)
            continue;
        if(i < j)
        {
            for(int k = j - 1; k >= i; k--)
                ret++, swap(a[k], a[k + 1]);
        }
        else
        {
            assert(false);
            for(int k = i; k - 1 >= j; k--)
                ret++, swap(a[k - 1], a[k]);
        }
    }

    return ret;
}

ll brute(vector<int> &v)
{

    vector<int> p(v);
    sort(p.begin(), p.end());

    ll ans = LLONG_MAX;
    do
    {
        if(valid(p))
            ans = min(ans, dist(v, p));

    } while(next_permutation(p.begin(), p.end()));

    return ans;
}

signed main()
{
    FIO
    int T = 1;
//    doWork({2, 3, 4, 1, 5, 6});
//    cin >> T;
    for(int i = 1; i <= T; i++)
    {
        int n;
        cin >> n;
        vector<int> v(n);
        for(auto &it: v)
            cin >> it;
        cout << doWork2(v);

//        int n = 7;
//        vector<int> p(n);
//        iota(p.begin(), p.end(), 1);
//        do
//        {
//
//            if(brute(p) != doWork2(p))
//            {
//                cout << n << '\n';
//                for(auto &it: p)
//                    cout << it << ' ';
//                cout << "\nBrute: " << brute(p) << '\n';
//                cout << "Hazem: " << doWork(p) << '\n';
//                cout << "Hesham: " << doWork2(p) << '\n';
//
//                exit(0);
//            }
//        } while(next_permutation(p.begin(), p.end()));

    }
}