#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;
}



Measured memory_bytes: 12460