#include<bits/stdc++.h>
#define ll long long
#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define ioss ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define getbit(i,j) ((i>>j)&1)
#define cnt_bit(x) __builtin_popcount(x)
#define cnt_bit_ll(x) __builtin_popcountll(x)
#define prefix_sum(a,pos,n) partial_sum(a + pos, a + n + 1, a + pos);
#define difference_array(a,pos) adjacent_difference(a + pos, a + n + 1, a + pos);
#define LOG 20
using namespace std;
const int dx[]={-1,0,1,0};
const int dy[]={0,1,0,-1};
const int N=1e6+5;
const int mod = 1e9+7;
const ll oo = 1e17+7;
bool maximize(int &x, int y){if (x<y){x=y;return 1;}return 0;}
bool minimize(int &x, int y){if (x>y){x=y;return 1;}return 0;}
void add(int &x, const int &y) {x += y;if (x >= mod) x -= mod;}
void sub(int &x, const int &y) {x -= y;if (x < 0) x += mod;}
typedef pair< int ,  int > ii;
typedef pair<ii , ll> iii;
struct edge {
    int u,v,c;
    edge(){}
    edge(const int &_u,const int &_v,const int &_c) {
        u=_u;v=_v;c=_c;
    }
    bool operator < (const edge &x) const {
        return (c<x.c);
    }
};

int mer(int a[],int be,int en,int ty)
{
    if (en-be==1)
    {
        if (ty)
        {
            if (a[be]<a[en])
                return 1;
            return 0;
        }
        else
        {
            if (a[be]>a[en])
                return 1;
            return 0;
        }
    }

    int t=0, mx = a[be] , mn=a[en] , mid = (be+en)/2;
    for (int i=be;i<=en;i++)
        mx = max(mx,a[i]) , mn = min(mn,a[i]);

    queue<int> p;
    for (int i=be;i<=en;i++)
    {
        if (a[i]>(mx+mn)/2)
            p.push(i);
        else
        {
            if (!p.empty())
            {
                t+=i-p.front();
                p.pop();
                p.push(i);
            }
        }
    }
    while (!p.empty())
        p.pop();
    vector<int> q;
    for (int i=be;i<=en;i++)
    {
        if (a[i]<=(mx+mn)/2)
            q.pb(a[i]);
    }
    for (int i=be;i<=en;i++)
    {
        if (a[i]>(mx+mn)/2)
            q.pb(a[i]);
    }

    for (int i=be;i<=en;i++)
        a[i] = q[i-be];
    q.clear();
    //cout<<be<<" "<<en<<" "<<a[be]<<" "<<a[en]<<" : "<<t<<"\n";
    return t+mer(a,be,mid,ty)+mer(a,mid+1,en,ty);
}

int len[600005];
int G1[305],G2[305];

void mer1(int a[],int be,int en)
{
    int l = len[en-be+1];
    if (en-be==1)
    {
        if (a[be]>a[en])
            G1[l]+=1;
        else
            G2[l]+=1;

       return ;
    }

    int t1=0 , t2=0 , mx = a[be] , mn=a[en] , mid = (be+en)/2;
    for (int i=be;i<=en;i++)
        mx = max(mx,a[i]) , mn = min(mn,a[i]);

    queue<int> p;

    for (int i=be;i<=en;i++)
    {
        if (a[i]>(mx+mn)/2)
            p.push(i);
        else
        {
            if (!p.empty())
            {
                t1+=i-p.front();
                p.pop();
                p.push(i);
            }
        }
    }
    while (!p.empty())
        p.pop();

    for (int i=be;i<=en;i++)
    {
        if (a[i]<=(mx+mn)/2)
            p.push(i);
        else
        {
            if (!p.empty())
            {
                t2+=i-p.front();
                p.pop();
                p.push(i);
            }
        }
    }
    while (!p.empty())
        p.pop();


    vector<int> q;
    for (int i=be;i<=en;i++)
    {
        if (a[i]<=(mx+mn)/2)
            q.pb(a[i]);
    }
    for (int i=be;i<=en;i++)
    {
        if (a[i]>(mx+mn)/2)
            q.pb(a[i]);
    }

    for (int i=be;i<=en;i++)
        a[i] = q[i-be];

    G1[l] += t1;
    G2[l] += t2;

    mer1(a,be,mid);
    mer1(a,mid+1,en);

}

int main()
{
    ioss
    int t = 1;
    for (int i=1;i<=18;i++)
        t*=2 , len[t] = i;

    int n;
    cin>>n;
    int a[n+2],b[n+2],c[n+2];
    for (int i=1;i<=n;i++)
        cin>>a[i],b[i]=a[i],c[i]=a[i];


    int kq = mer(c,1,n,0);
    mer1(a,1,n);
    t=1;
    //cout<<kq<<"\n";
    for (int i=1;i<=len[n];i++)
        t+=min(G1[i],G2[i]);
    cout<<min(kq,t);//min(mer(c,1,n,0),min(mer1(a,1,n,1),mer1(b,1,n,0))+1);
}