 #include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define ALL(x) x.begin(),x.end()
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;

inline bool LT(double a,double b) { return !equals(a,b) && a < b; }
inline bool LTE(double a,double b) { return equals(a,b) || a < b; }

const int IINF = INT_MAX;
const char EMPTY = 'X';
 
struct Node{
  int value;
  char lazy;
  int lazy_coef; 
  Node(int value=0,char lazy=EMPTY,int lazy_coef=0):value(value),lazy(lazy),lazy_coef(lazy_coef){}
};
 
class MixSegmentTree{
public:
  vector<Node> RMQ;
  vector<int> minimum_dat,maximum_dat;
  int limit,N;
 
  void init(int tmp){
    N = tmp;
    int N_N = 1;
    while(N_N < N)N_N *= 2;
    limit = N_N;
    RMQ.resize(3*limit);
    minimum_dat.resize(3*limit);
    maximum_dat.resize(3*limit);
    rep(i,3*limit-1) {
      RMQ[i] = Node();
      minimum_dat[i] =  IINF;
      maximum_dat[i] = -IINF;
    }
  }

  tuple<int,int,int> _build(int cur,int L,int R,const vector<int> &buf){

    if( !( 0 <= cur && cur < 2*limit-1 ) ) return tuple<int,int,int>(0,IINF,-IINF);
    if( L == R-1 ){
      if( L >= N ) return tuple<int,int,int>(0,IINF,-IINF);
      RMQ[cur].value = buf[L];
      minimum_dat[cur] = buf[L];
      maximum_dat[cur] = buf[L];
    } else {
      tuple<int,int,int> vl = _build(cur*2+1,L,(L+R)/2,buf);
      tuple<int,int,int> vr = _build(cur*2+2,(L+R)/2,R,buf);
      RMQ[cur].value = get<0>(vl) + get<0>(vr);
      minimum_dat[cur] = min(get<1>(vl),get<1>(vr));
      maximum_dat[cur] = max(get<2>(vl),get<2>(vr));
    }
    return tuple<int,int,int>(RMQ[cur].value,minimum_dat[cur],maximum_dat[cur]);
  }

  void build(const vector<int> &buf) { _build(0,0,limit,buf); }

  inline void value_evaluate(int index,int L,int R){
    if( RMQ[index].lazy == 'A' ){
      RMQ[index].value += ( R - L ) * RMQ[index].lazy_coef;
      minimum_dat[index] += RMQ[index].lazy_coef;
      maximum_dat[index] += RMQ[index].lazy_coef;
    } else if( RMQ[index].lazy == 'S' ){
      RMQ[index].value = ( R - L ) * RMQ[index].lazy_coef;
      minimum_dat[index] = RMQ[index].lazy_coef;
      maximum_dat[index] = RMQ[index].lazy_coef;
    }
  }
   
  inline void lazy_evaluate(int index,int L,int R){
    value_evaluate(index,L,R);
    if( index < limit && RMQ[index].lazy != EMPTY ) {
      if( RMQ[index].lazy == 'A' ) {
        if( RMQ[index*2+1].lazy == EMPTY ) RMQ[index*2+1].lazy = 'A'; 
        if( RMQ[index*2+2].lazy == EMPTY ) RMQ[index*2+2].lazy = 'A';
        RMQ[index*2+1].lazy_coef += RMQ[index].lazy_coef;
        RMQ[index*2+2].lazy_coef += RMQ[index].lazy_coef;
      } else if( RMQ[index].lazy == 'S') {
        RMQ[index*2+1].lazy = RMQ[index*2+2].lazy = 'S';
        RMQ[index*2+1].lazy_coef = RMQ[index].lazy_coef;
        RMQ[index*2+2].lazy_coef = RMQ[index].lazy_coef;
      }
    }
    RMQ[index].lazy = EMPTY;
    RMQ[index].lazy_coef = 0;
  }
 
  inline void value_update(int index){
    RMQ[index].value = RMQ[index*2+1].value + RMQ[index*2+2].value;
    minimum_dat[index] = min(minimum_dat[index*2+1],minimum_dat[index*2+2]);
    maximum_dat[index] = max(maximum_dat[index*2+1],maximum_dat[index*2+2]);
  }
 
  void _update(int a,int b,char opr,int v,int index,int L,int R){
    lazy_evaluate(index,L,R);
 
    if( b <= L || R <= a )return;
    if( a <= L && R <= b ){
      RMQ[index].lazy = opr;
      if( opr == 'A' )      RMQ[index].lazy_coef += v; 
      else if( opr == 'S' ) RMQ[index].lazy_coef = v; 
      lazy_evaluate(index,L,R);
      return;
    }
 
    _update(a,b,opr,v,index*2+1,L,(L+R)/2);
    _update(a,b,opr,v,index*2+2,(L+R)/2,R);
    value_update(index);
 
  }

  void update(int a,int b,char opr,int v){ _update(a,b,opr,v,0,0,limit); } 

  tuple<int,int,int> _query(int a,int b,int index,int L,int R){
    lazy_evaluate(index,L,R);
 
    if( b <= L || R <= a ) return make_tuple(0,IINF,-IINF);
    if( a <= L && R <= b ) return make_tuple(RMQ[index].value,minimum_dat[index],maximum_dat[index]);


    auto tmp1 = _query(a,b,index*2+1,L,(L+R)/2);
    auto tmp2 = _query(a,b,index*2+2,(L+R)/2,R);
    tuple<int,int,int> ret = make_tuple(get<0>(tmp1)+get<0>(tmp2),min(get<1>(tmp1),get<1>(tmp2)),max(get<2>(tmp1),get<2>(tmp2)));
    value_update(index); 
    return ret;
  }

  tuple<int,int,int> query(int a,int b) { return _query(a,b,0,0,limit); }

};

struct Data {
  int v, pos;
  bool operator < ( const Data &d ) const {
    return v < d.v;
  }
};

int n;
vector<int> a;

void compute() {
  MixSegmentTree rmq;
  {
    rmq.init(n);
    vector<int> ones(n,1);
    rmq.build(ones);
  }
  vector<Data> vec;
  rep(i,n) vec.push_back((Data){a[i],i});
  sort(ALL(vec));
  ll ans = 0;
  rep(i,n) {
    int j = i;
    while( j < n && vec[i].v == vec[j].v ) {
      ++j;
    }
    REP(k,i,j) {
      rmq.update(vec[k].pos,vec[k].pos+1,'S',0);
    }
    REP(k,i,j) {
      ll mini = LLONG_MAX;
      if( 0 == vec[k].pos ) mini = 0;
      else {
	auto tmp = rmq.query(0, vec[k].pos);
	mini = min(mini, (ll)get<0>(tmp));
      }
      if( n == vec[k].pos+1 ) {
	mini = 0;
      } else {
	auto tmp = rmq.query(vec[k].pos+1,n);
	mini = min(mini, (ll)get<0>(tmp));
      }
      ans += mini;
    }
    i = j - 1;
  }
  cout << ans << endl;
}

int main() {
  cin >> n;
  a.resize(n);
  rep(i,n) cin >> a[i];
  compute();
  return 0;
}


### Prompt

Generate 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>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define ALL(x) x.begin(),x.end()
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;

inline bool LT(double a,double b) { return !equals(a,b) && a < b; }
inline bool LTE(double a,double b) { return equals(a,b) || a < b; }

const int IINF = INT_MAX;
const char EMPTY = 'X';
 
struct Node{
  int value;
  char lazy;
  int lazy_coef; 
  Node(int value=0,char lazy=EMPTY,int lazy_coef=0):value(value),lazy(lazy),lazy_coef(lazy_coef){}
};
 
class MixSegmentTree{
public:
  vector<Node> RMQ;
  vector<int> minimum_dat,maximum_dat;
  int limit,N;
 
  void init(int tmp){
    N = tmp;
    int N_N = 1;
    while(N_N < N)N_N *= 2;
    limit = N_N;
    RMQ.resize(3*limit);
    minimum_dat.resize(3*limit);
    maximum_dat.resize(3*limit);
    rep(i,3*limit-1) {
      RMQ[i] = Node();
      minimum_dat[i] =  IINF;
      maximum_dat[i] = -IINF;
    }
  }

  tuple<int,int,int> _build(int cur,int L,int R,const vector<int> &buf){

    if( !( 0 <= cur && cur < 2*limit-1 ) ) return tuple<int,int,int>(0,IINF,-IINF);
    if( L == R-1 ){
      if( L >= N ) return tuple<int,int,int>(0,IINF,-IINF);
      RMQ[cur].value = buf[L];
      minimum_dat[cur] = buf[L];
      maximum_dat[cur] = buf[L];
    } else {
      tuple<int,int,int> vl = _build(cur*2+1,L,(L+R)/2,buf);
      tuple<int,int,int> vr = _build(cur*2+2,(L+R)/2,R,buf);
      RMQ[cur].value = get<0>(vl) + get<0>(vr);
      minimum_dat[cur] = min(get<1>(vl),get<1>(vr));
      maximum_dat[cur] = max(get<2>(vl),get<2>(vr));
    }
    return tuple<int,int,int>(RMQ[cur].value,minimum_dat[cur],maximum_dat[cur]);
  }

  void build(const vector<int> &buf) { _build(0,0,limit,buf); }

  inline void value_evaluate(int index,int L,int R){
    if( RMQ[index].lazy == 'A' ){
      RMQ[index].value += ( R - L ) * RMQ[index].lazy_coef;
      minimum_dat[index] += RMQ[index].lazy_coef;
      maximum_dat[index] += RMQ[index].lazy_coef;
    } else if( RMQ[index].lazy == 'S' ){
      RMQ[index].value = ( R - L ) * RMQ[index].lazy_coef;
      minimum_dat[index] = RMQ[index].lazy_coef;
      maximum_dat[index] = RMQ[index].lazy_coef;
    }
  }
   
  inline void lazy_evaluate(int index,int L,int R){
    value_evaluate(index,L,R);
    if( index < limit && RMQ[index].lazy != EMPTY ) {
      if( RMQ[index].lazy == 'A' ) {
        if( RMQ[index*2+1].lazy == EMPTY ) RMQ[index*2+1].lazy = 'A'; 
        if( RMQ[index*2+2].lazy == EMPTY ) RMQ[index*2+2].lazy = 'A';
        RMQ[index*2+1].lazy_coef += RMQ[index].lazy_coef;
        RMQ[index*2+2].lazy_coef += RMQ[index].lazy_coef;
      } else if( RMQ[index].lazy == 'S') {
        RMQ[index*2+1].lazy = RMQ[index*2+2].lazy = 'S';
        RMQ[index*2+1].lazy_coef = RMQ[index].lazy_coef;
        RMQ[index*2+2].lazy_coef = RMQ[index].lazy_coef;
      }
    }
    RMQ[index].lazy = EMPTY;
    RMQ[index].lazy_coef = 0;
  }
 
  inline void value_update(int index){
    RMQ[index].value = RMQ[index*2+1].value + RMQ[index*2+2].value;
    minimum_dat[index] = min(minimum_dat[index*2+1],minimum_dat[index*2+2]);
    maximum_dat[index] = max(maximum_dat[index*2+1],maximum_dat[index*2+2]);
  }
 
  void _update(int a,int b,char opr,int v,int index,int L,int R){
    lazy_evaluate(index,L,R);
 
    if( b <= L || R <= a )return;
    if( a <= L && R <= b ){
      RMQ[index].lazy = opr;
      if( opr == 'A' )      RMQ[index].lazy_coef += v; 
      else if( opr == 'S' ) RMQ[index].lazy_coef = v; 
      lazy_evaluate(index,L,R);
      return;
    }
 
    _update(a,b,opr,v,index*2+1,L,(L+R)/2);
    _update(a,b,opr,v,index*2+2,(L+R)/2,R);
    value_update(index);
 
  }

  void update(int a,int b,char opr,int v){ _update(a,b,opr,v,0,0,limit); } 

  tuple<int,int,int> _query(int a,int b,int index,int L,int R){
    lazy_evaluate(index,L,R);
 
    if( b <= L || R <= a ) return make_tuple(0,IINF,-IINF);
    if( a <= L && R <= b ) return make_tuple(RMQ[index].value,minimum_dat[index],maximum_dat[index]);


    auto tmp1 = _query(a,b,index*2+1,L,(L+R)/2);
    auto tmp2 = _query(a,b,index*2+2,(L+R)/2,R);
    tuple<int,int,int> ret = make_tuple(get<0>(tmp1)+get<0>(tmp2),min(get<1>(tmp1),get<1>(tmp2)),max(get<2>(tmp1),get<2>(tmp2)));
    value_update(index); 
    return ret;
  }

  tuple<int,int,int> query(int a,int b) { return _query(a,b,0,0,limit); }

};

struct Data {
  int v, pos;
  bool operator < ( const Data &d ) const {
    return v < d.v;
  }
};

int n;
vector<int> a;

void compute() {
  MixSegmentTree rmq;
  {
    rmq.init(n);
    vector<int> ones(n,1);
    rmq.build(ones);
  }
  vector<Data> vec;
  rep(i,n) vec.push_back((Data){a[i],i});
  sort(ALL(vec));
  ll ans = 0;
  rep(i,n) {
    int j = i;
    while( j < n && vec[i].v == vec[j].v ) {
      ++j;
    }
    REP(k,i,j) {
      rmq.update(vec[k].pos,vec[k].pos+1,'S',0);
    }
    REP(k,i,j) {
      ll mini = LLONG_MAX;
      if( 0 == vec[k].pos ) mini = 0;
      else {
	auto tmp = rmq.query(0, vec[k].pos);
	mini = min(mini, (ll)get<0>(tmp));
      }
      if( n == vec[k].pos+1 ) {
	mini = 0;
      } else {
	auto tmp = rmq.query(vec[k].pos+1,n);
	mini = min(mini, (ll)get<0>(tmp));
      }
      ans += mini;
    }
    i = j - 1;
  }
  cout << ans << endl;
}

int main() {
  cin >> n;
  a.resize(n);
  rep(i,n) cin >> a[i];
  compute();
  return 0;
}


```