Description

对家庭菜园有兴趣的 JOI 君每年在自家的田地中种植一种叫做 IOI 草的植物. JOI 君的田地沿东西方向被划分为 \(n\) 个区域, 由西到东标号为 \(1 - n\). IOI 草一共有 \(n\) 株, 每个区域 种植着一株. 在第 \(i\) 个区域种植的 IOI 草, 在春天的时候高度会生长至 \(h_i\), 此后便不再生长.

为了观察春天的样子而出行的 JOI 君注意到了 IOI 草的配置与预定的不太一样. IOI 草是一种 非常依靠阳光的植物, 如果某个区域的 IOI 草的东侧和西侧都有比它高的 IOI 草存在, 那么 这株 IOI 草就会在夏天之前枯萎. 换句话说, 为了不让任何一株 IOI 草枯萎, 需要满足以下条件:

对于任意 \(2 \leq i \leq n-1\), 以下两个条件至少满足一个:

  1. \(\forall 1 \leq j \leq i-1, h_j \leq h_i\)
  2. \(\forall i+1 \leq k \leq n, h_k \leq h_i\)

IOI 草是非常昂贵的, 为了不让 IOI 草枯萎, JOI 君需要调换 IOI 草的顺序. IOI 草非常非常的 高大且纤细的植物, 因此 JOI 君每次只能交换相邻两株 IOI 草. 也就是说, JOI 君每次需要选择一个整数 \(i (1 \leq i \leq n-1)\), 然后交换第 \(i\) 株 IOI 草和第 \(i+1\) 株 IOI 草. 随着 夏天临近, IOI 草枯萎的可能性越来越大, 因此 JOI 君想知道让所有 IOI 草都不会枯萎的最少操作次数.

现在给出田地的区域数, 以及每株 IOI 草的高度, 请你求出让所有 IOI 草的不会枯萎的最少操作次数.

Input

第一行一个正整数 \(n\), 代表田地被分为了 \(n\) 个区域.

接下来 \(n\) 行, 第 \(i\) 行 \((1 \leq i \leq n)\) 一个整数 \(h_i\), 表示第 \(i\) 株植物在 春天时的高度.

Output

输出一行一个整数, 表示最少需要的操作次数.

Sample Input

6
2
8
4
5
3
6

Sample Output

3

Data Range

对于所有数据, 满足:\(3 \leq n \leq 3 \times 10^5, 1 \leq h_i \leq 10^9\)

Explanation

首先一个足够高的植物一定不会影响到更高的植物对吧......

然后极端地来看像最高的那一棵到哪里都会招人恨对不对......

然后贪心地我们发现一棵植物必须要么向左要么向右移动, 移动的距离就是左边比他高一点 的最靠左的那一棵植物, 右边同理. 然后发现其实就是每一次贪心一下, 用树状数组或者线段树记录一下就可以了.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 300100;

class BinaryIndexedTree
{
public:
    int n, arr[maxn];
    void change(int x, int v)
    {
        for (; x > 0; x -= x&-x)
            arr[x] += v;
        return ;
    }
    int query(int x)
    {
        int res = 0;
        for (; x <= n; x += x&-x)
            res += arr[x];
        return res;
    }
    void clear(void)
    {
        n = 0;
        memset(arr, 0, sizeof(arr));
        return ;
    }
} bit;

int n, n__, a[maxn];
pair<int, int> b[maxn];
int l[maxn], r[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &b[i].first);
        b[i].second = i;
    }
    sort(b + 1, b + n + 1);
    n__ = 0;
    for (int i = 1; i <= n; i++) {
        if (i == 1 || b[i].first != b[i-1].first)
            n__ += 1;
        a[b[i].second] = n__;
    }
    // Inserting
    bit.n = n__;
    for (int i = 1; i <= n; i++) {
        bit.change(a[i], 1);
        l[i] = bit.query(a[i] + 1);
    }
    bit.clear();
    // Inserting, reversed.
    bit.n = n__;
    for (int i = n; i >= 1; i--) {
        bit.change(a[i], 1);
        r[i] = bit.query(a[i] + 1);
    }
    // Generate output
    lli res = 0;
    for (int i = 1; i <= n; i++)
        res += min(l[i], r[i]);
    printf("%lld\n", res);
    return 0;
}