题意描述

休息的时候，可以放松放松浑身的肌肉，打扫打扫卫生，感觉很舒服。

在某一天，某LMZ开始整理他那书架。已知他的书有$n$本，从左到右按顺序排列。

他想把书从矮到高排好序，而每一本书都有一个独一无二的高度$h_i$。

他排序的方法是：每一次将所有的书划分为尽量少的连续部分，使得每一部分的书的高度都是单调下降，然后将其中所有不少于$2$本书的区间全部翻转。重复执行以上操作，最后使得书的高度全部单调上升。

可是毕竟是休息时间，LMZ不想花太多时间在给书排序这种事上面。

因此他划分并翻转完第一次书之后，他想计算，他一共执行了多少次翻转操作才能把所有的书排好序。

LMZ惊奇地发现，第一次排序之前，他第一次划分出来的所有区间的长度都是偶数。

输入格式

第一行一个正整数$n$, 为书的总数。

接下来一行$n$个数，第$i$个正整数$h_i$，为第$i$本书的高度。

输出格式

输出仅一个整数，为LMZ需要做的翻转操作的次数。

Input & Output ‘s examples

Input ‘s eg

6
5 3 2 1 6 4

Output ‘s eg

样例解释

第一次划分之后，翻转$\lbrack 5,3,2,1 \rbrack$，$\lbrack 6,4 \rbrack$。之后，书的高度为$1 , 2 , 3 , 5 , 4 , 6$，然后便是翻转$\lbrack 5,4 \rbrack$即可。

数据范围与约定

对于$10\%$的数据：$n<=50$

对于$40\%$的数据：$n<=3\times 10^3$

对于$100\%$的数据：$1<=n<=10^5, 1<=h_i<=n$

分析

一道比较显然的结论题。

先说解法。首先，找出所有的单调下降序列，然后把他们全部翻转过来，记录翻转的次数。

之后求出翻转后序列的逆序对数，答案就是逆序对数与翻转次数之和。

证明如下：

在找出所有的单调下降序列并翻转后，可以发现，刚刚找到的区间内的元素都已经变得有序。

也就是说，只有两个小区间之间的数可以进行交换。

显然，我们只会交换两个降序的数。即逆序对。

因此答案为逆序对数与翻转次数之和。

剩下的见代码注释。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 100001

using namespace std;

int n , m , s;

namespace Tree_array{
    ll tree[N];

    int lowbit(int x){
        return x & (- x);
    }

    I void add(int x , ll val){
        for(int i = x; i <= n; i += lowbit(i)){
            tree[i] += val;
        }
    }

    I ll query(int x){
        ll ans = 0;
        for(int i = x; i ; i -= lowbit(i)){
            ans += tree[i];
        }
        return ans;
    }

}

ll a[N] , b[N] , ans = 0;

I void input(){     //离散化输入数据
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1 , b + 1 + n);
    ll number = unique(b + 1 , b + 1 + n) - b - 1;
    for(int i = 1; i <= n; i ++){
        a[i] = lower_bound(b + 1 , b + 1 + number , a[i]) - b;
    }
}

int main(){
    input();
    ll l = 1 , r = 1;
    for(int i = 1; i <= n; i ++){   //手动模拟，找出单调下降序列
        if(i < n && a[i] > a[i + 1]){
            r ++;
        }
        else{
            if(l < r){
                while(l < r){
                    swap(a[l] , a[r]);
                    l ++ , r --;
                }
                ans ++;
            }
            l = r = i + 1;
        }
    }
    for(int i = 1; i <= n; i ++){   //树状数组求逆序对数
        Tree_array :: add(a[i] , 1);
        ans += i - Tree_array :: query(a[i]);
    }
    cout << ans << "\n";
    return 0;
}