//#include <bits/stdc++.h>

#include <iostream>
#include <algorithm>

#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <cstring>
#include <string>
#include <utility>
#include <array>
#include <complex>
#include <valarray>

#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <chrono>
#include <random>
#include <numeric>


using namespace std;
#define int long long

typedef long long ll;
typedef unsigned long long ull;
//typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double,int> pdi;
typedef pair<long double, int> pdbi;
typedef pair<int,pii> pipii;
typedef pair<ll,pll> plpll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
typedef vector<vector<int>> mat;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const int INF = 1<<30;
const ll INFLL = 1LL<<62;
const long double EPS = 1e-12;
const ll mod = 1000000000 + 7;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const long double pi = 3.141592653589793;

#define addm(X, Y) (X) = ((X) + ((Y) % mod) + mod) % mod
#define inside(y, x, h, w) (0 <= (y) && (y) < (h) && 0 <= (x) && (x) < (w)) ? true : false

//debug
#define DEBUG

#define DUMPOUT cout

#ifdef DEBUG
#define dump(...) DUMPOUT<<#__VA_ARGS__<<" :["<<__FUNCTION__<<":"<<__LINE__<<"]"<<endl; DUMPOUT<<"    "; dump_func(__VA_ARGS__)
#else
#define dump(...)
#endif

void dump_func() {DUMPOUT << endl;};

template <class Head, class... Tail> void dump_func(Head&& head, Tail&&... tail) {
    DUMPOUT << head;
    if (sizeof...(Tail) == 0) DUMPOUT << " ";
    else DUMPOUT << ", ";
    dump_func(std::move(tail)...);
}

//ostream
template<typename T> ostream& operator << (ostream& os, vector<T>& vec) {
    os << "["; for (int i = 0; i<vec.size(); i++) os << vec[i] << (i + 1 == vec.size() ? "" : ", "); os << "]";
    return os;
}

template<typename T, typename U> ostream& operator << (ostream& os, pair<T, U>& pair_var) {
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}

template<typename T, typename U> ostream& operator << (ostream& os, map<T, U>& map_var) {
    os << "[";
    for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
        os << "(" << itr->first << ", " << itr->second << ")"; itr++;  if(itr != map_var.end()) os << ", "; itr--;
    }
    os << "]";
    return os;
}

template<typename T> ostream& operator << (ostream& os, set<T>& set_var) {
    os << "[";
    for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
        os << *itr; ++itr; if(itr != set_var.end()) os << ", "; itr--;
    }
    os << "]";
    return os;
}

int n;
int a[100000 + 5];
vector<vector<int>> v(100000 + 5);

struct BIT {
    int size;
    vector<int> node;

    BIT(int n, long long init_num) {
        size = n;
        node.resize(size + 1, init_num);
    }

    void add(int i, long long x) {
        while (i <= size) {
            node[i] += x;
            i += i & -i;
        }
    }

    long long sum(int i) {
        long long ret = 0;
        while (i > 0) {
            ret += node[i];
            i -= i & -i;
        }
        return ret;
    }
};

BIT bitl(100000 + 5, 0), bitr(100000 + 5, 0);
int ans = 0;
int mx = 0;

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n;
  rep(i, n) {
    cin >> a[i];
    v[a[i]].push_back(i + 1);
    mx = max(mx, a[i]);
  }
  int l = 1;
  int r = n;
  rep2(i, 1, mx) {
    vector<int> pos = v[i];
    if (pos.size() == 0) continue;
    rep(j, pos.size()) {
      int prepos = pos[j];
      pos[j] += bitl.sum(100000 + 1) - bitl.sum(prepos);
      pos[j] -= bitr.sum(prepos);
    }
    int mnd = 0;
    int tmpr = r;
    vector<int> cost(pos.size());
    rrep2(j, pos.size() - 1, -1) {
      mnd += tmpr - pos[j];
      cost[j] = tmpr - pos[j];
      tmpr--;
    }
    int tmpl = l;
    int tmpmnd = mnd;
    int m = -1;
    rep(j, pos.size()) {
      tmpmnd -= cost[j];
      tmpmnd += pos[j] - tmpl;
      if (mnd > tmpmnd) {
        tmpl++;
        mnd = tmpmnd;
        tmpr++;
        m = j;
      }
      else break;
    }
    rep(j, pos.size()) {
      //cout << v[i][j] << endl;
      if (j <= m) bitl.add(v[i][j], 1);
      else bitr.add(v[i][j], 1);
    }
    ans += mnd;
    l = tmpl;
    r = tmpr;
  }
  cout << ans << endl;
}


### Prompt

Please formulate a CPP solution to the following problem:

What Goes Up Must Come Down

Several cards with numbers printed on them are lined up on the table.

We'd like to change their order so that first some are in non-decreasing order of the numbers on them, and the rest are in non-increasing order. For example, (1, 2, 3, 2, 1), (1, 1, 3, 4, 5, 9, 2), and (5, 3, 1) are acceptable orders, but (8, 7, 9) and (5, 3, 5, 3) are not.

To put it formally, with $n$ the number of cards and $b_i$ the number printed on the card at the $i$-th position ($1 \leq i \leq n$) after reordering, there should exist $k \in \\{1, ... n\\}$ such that ($b_i \leq b_{i+1} \forall _i \in \\{1, ... k - 1\\}$) and ($b_i \geq b_{i+1} \forall _i \in \\{k, ..., n - 1\\}$) hold.

For reordering, the only operation allowed at a time is to swap the positions of an adjacent card pair. We want to know the minimum number of swaps required to complete the reorder.

Input

The input consists of a single test case of the following format.


$n$
$a_1$ ... $a_n$


An integer $n$ in the first line is the number of cards ($1 \leq n \leq 100 000$). Integers $a_1$ through $a_n$ in the second line are the numbers printed on the cards, in the order of their original positions ($1 \leq a_i \leq 100 000$).

Output

Output in a line the minimum number of swaps required to reorder the cards as specified.

Sample Input 1


7
3 1 4 1 5 9 2


Sample Output 1


3


Sample Input 2


9
10 4 6 3 15 9 1 1 12


Sample Output 2


8


Sample Input 3


8
9 9 8 8 7 7 6 6


Sample Output 3


0


Sample Input 4


6
8 7 2 5 4 6


Sample Output 4


4






Example

Input

7
3 1 4 1 5 9 2


Output

3

### Response

```cpp
//#include <bits/stdc++.h>

#include <iostream>
#include <algorithm>

#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <cstring>
#include <string>
#include <utility>
#include <array>
#include <complex>
#include <valarray>

#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <chrono>
#include <random>
#include <numeric>


using namespace std;
#define int long long

typedef long long ll;
typedef unsigned long long ull;
//typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double,int> pdi;
typedef pair<long double, int> pdbi;
typedef pair<int,pii> pipii;
typedef pair<ll,pll> plpll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
typedef vector<vector<int>> mat;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const int INF = 1<<30;
const ll INFLL = 1LL<<62;
const long double EPS = 1e-12;
const ll mod = 1000000000 + 7;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const long double pi = 3.141592653589793;

#define addm(X, Y) (X) = ((X) + ((Y) % mod) + mod) % mod
#define inside(y, x, h, w) (0 <= (y) && (y) < (h) && 0 <= (x) && (x) < (w)) ? true : false

//debug
#define DEBUG

#define DUMPOUT cout

#ifdef DEBUG
#define dump(...) DUMPOUT<<#__VA_ARGS__<<" :["<<__FUNCTION__<<":"<<__LINE__<<"]"<<endl; DUMPOUT<<"    "; dump_func(__VA_ARGS__)
#else
#define dump(...)
#endif

void dump_func() {DUMPOUT << endl;};

template <class Head, class... Tail> void dump_func(Head&& head, Tail&&... tail) {
    DUMPOUT << head;
    if (sizeof...(Tail) == 0) DUMPOUT << " ";
    else DUMPOUT << ", ";
    dump_func(std::move(tail)...);
}

//ostream
template<typename T> ostream& operator << (ostream& os, vector<T>& vec) {
    os << "["; for (int i = 0; i<vec.size(); i++) os << vec[i] << (i + 1 == vec.size() ? "" : ", "); os << "]";
    return os;
}

template<typename T, typename U> ostream& operator << (ostream& os, pair<T, U>& pair_var) {
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}

template<typename T, typename U> ostream& operator << (ostream& os, map<T, U>& map_var) {
    os << "[";
    for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
        os << "(" << itr->first << ", " << itr->second << ")"; itr++;  if(itr != map_var.end()) os << ", "; itr--;
    }
    os << "]";
    return os;
}

template<typename T> ostream& operator << (ostream& os, set<T>& set_var) {
    os << "[";
    for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
        os << *itr; ++itr; if(itr != set_var.end()) os << ", "; itr--;
    }
    os << "]";
    return os;
}

int n;
int a[100000 + 5];
vector<vector<int>> v(100000 + 5);

struct BIT {
    int size;
    vector<int> node;

    BIT(int n, long long init_num) {
        size = n;
        node.resize(size + 1, init_num);
    }

    void add(int i, long long x) {
        while (i <= size) {
            node[i] += x;
            i += i & -i;
        }
    }

    long long sum(int i) {
        long long ret = 0;
        while (i > 0) {
            ret += node[i];
            i -= i & -i;
        }
        return ret;
    }
};

BIT bitl(100000 + 5, 0), bitr(100000 + 5, 0);
int ans = 0;
int mx = 0;

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n;
  rep(i, n) {
    cin >> a[i];
    v[a[i]].push_back(i + 1);
    mx = max(mx, a[i]);
  }
  int l = 1;
  int r = n;
  rep2(i, 1, mx) {
    vector<int> pos = v[i];
    if (pos.size() == 0) continue;
    rep(j, pos.size()) {
      int prepos = pos[j];
      pos[j] += bitl.sum(100000 + 1) - bitl.sum(prepos);
      pos[j] -= bitr.sum(prepos);
    }
    int mnd = 0;
    int tmpr = r;
    vector<int> cost(pos.size());
    rrep2(j, pos.size() - 1, -1) {
      mnd += tmpr - pos[j];
      cost[j] = tmpr - pos[j];
      tmpr--;
    }
    int tmpl = l;
    int tmpmnd = mnd;
    int m = -1;
    rep(j, pos.size()) {
      tmpmnd -= cost[j];
      tmpmnd += pos[j] - tmpl;
      if (mnd > tmpmnd) {
        tmpl++;
        mnd = tmpmnd;
        tmpr++;
        m = j;
      }
      else break;
    }
    rep(j, pos.size()) {
      //cout << v[i][j] << endl;
      if (j <= m) bitl.add(v[i][j], 1);
      else bitr.add(v[i][j], 1);
    }
    ans += mnd;
    l = tmpl;
    r = tmpr;
  }
  cout << ans << endl;
}


```