#include <bits/stdc++.h>
using namespace std;

const int64_t inf = 1001001001001001001ll;

template <typename T> class Compress {
private:
  size_t sz;
  std::vector<T> zip;
  std::vector<int> formatted;

public:
  Compress(std::vector<T> &v) : formatted(v.size(), -1), sz(v.size()) {
    zip = v;
    std::sort(zip.begin(), zip.end());
    zip.erase(std::unique(zip.begin(), zip.end()), zip.end());
    for (int i = 0; i < formatted.size(); ++i) {
      formatted[i] = std::lower_bound(zip.begin(), zip.end(), v[i]) - zip.begin();
    }
  }

  int operator[](size_t idx) {
    return formatted[idx];
  }

  T unzip(size_t idx) {
    assert(idx < zip.size());
    return zip[idx];
  }

  std::vector<int> get() {
    return formatted;
  }

  size_t size() {
    return sz;
  }
};

struct BinaryIndexedTree {
  BinaryIndexedTree(size_t n) : n(n), v(n + 1, 0) {}

  size_t n;
  vector<int64_t> v;

  int sum(int k) {
    int64_t ret = 0;
    for (; k; k -= k & -k) ret += v[k];
    return ret;
  }

  void add(int k, int x) {
    for (; k <= n; k += k & -k) v[k] += x;
  }
};

struct Node {
  int64_t node, lazy;
  Node() {}
  Node(int64_t node, int64_t lazy) : node(node), lazy(lazy) {}

  Node operator*(const Node &r) const {
    return Node(max(node, r.node), -inf);
  }
} e(0, -inf);

struct SegmentTree : Node {
  size_t n;
  vector<Node> seg;

  SegmentTree(size_t size) : n(1 << (32 - __builtin_clz(size - 1))), seg(2 * n - 1, e) {}

  inline void lazy_add(int k, int64_t x) {
    if (seg[k].lazy == -inf) {
      seg[k].lazy = 0;
    }
    seg[k].lazy += x;
  }

  inline void lazy_evaluate(int k) {
    if (seg[k].lazy != -inf) {
      seg[k].node += seg[k].lazy;
      if (k < n - 1) {
        lazy_add(2 * k + 1, seg[k].lazy);
        lazy_add(2 * k + 2, seg[k].lazy);
      }
      seg[k].lazy = -inf;
    }
  }

  inline void update_node(int k) {
    seg[k] = seg[2 * k + 1] * seg[2 * k + 2];
  }

  void add(int l, int r, int64_t x, int k, int a, int b) {
    lazy_evaluate(k);

    if (r <= a || b <= l) return;
    if (l <= a && b <= r) {
      lazy_add(k, x);
      lazy_evaluate(k);
      return;
    }

    add(l, r, x, 2 * k + 1, a, (a + b) / 2);
    add(l, r, x, 2 * k + 2, (a + b) / 2, b);
    update_node(k);
  }

  Node query(int l, int r, int k, int a, int b) {
    lazy_evaluate(k);
    if (r <= a || b <= l) return e;
    if (l <= a && b <= r) return seg[k];

    return query(l, r, 2 * k + 1, a, (a + b) / 2) * query(l, r, 2 * k + 2, (a + b) / 2, b);
  }

  void add(int l, int r, int64_t x) {
    // cerr << "range [" << l << ", " << r << ") add to " << x << endl;
    add(l, r, x, 0, 0, n);
  }

  int64_t query(int l, int r) {
    // cerr << "range [" << l << ", " << r << ") query of " << query(l, r, 0, 0, n).node << endl;
    return query(l, r, 0, 0, n).node;
  }

  void debug() {
    for (int i = 0; i < n; ++i) {
      cout << query(i, i + 1) << (i + 1 == n ? "\n" : " ");
    }
  }
};

signed main() {
  int n;
  cin >> n;

  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }

  Compress<int> zip(a);
  a = zip.get();

  int64_t inversion = 0;
  BinaryIndexedTree bit(n + 1);
  for (int64_t i = 0; i < n; ++i) {
    inversion += i - bit.sum(a[i] + 1);
    bit.add(a[i] + 1, 1);
  }

  // cerr << "inversion : " << inversion << endl;

  if (inversion == 0) {
    a.erase(unique(a.begin(), a.end()), a.end());

    cout << (a.size() == n) << endl;
    return 0;
  }

  int seg_size = 0, max_a = -1, min_a = 1001001001;
  vector<int> val, idx, top(n), bottom(n);
  for (int i = 0; i < n; ++i) {
    if (max_a < a[i]) {
      val.push_back(a[i]);
      idx.push_back(i);
      top[i] = 1;
      max_a = a[i];
      seg_size++;
    }
  }
  for (int i = n - 1; i >= 0; --i) {
    if (min_a > a[i]) {
      bottom[i] = 1;
      min_a = a[i];
    }
  }

  int64_t ans = inf;
  SegmentTree seg(seg_size);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  for (int i = 0; i < n; ++i) {
    if (!bottom[i]) {
      // cerr << i << " is the other." << endl;
      if (*lower_bound(val.begin(), val.end(), a[i]) == a[i]) {
        int index = lower_bound(val.begin(), val.end(), a[i]) - val.begin();
        seg.add(index, index + 1, 1);
      }
      int l = lower_bound(val.begin(), val.end(), a[i] + 1) - val.begin();
      int r = lower_bound(idx.begin(), idx.end(), i) - idx.begin();
      seg.add(l, r, 2);
      pq.push(make_pair(a[i], i));
    }
    if (bottom[i]) {
      // cerr << i << " is bottom." << endl;
      queue<pair<int, int>> q;
      while (!pq.empty() && pq.top().first <= a[i]) {
        pair<int, int> p = pq.top();
        pq.pop();

        if (a[i] == p.first) {
          int l = lower_bound(val.begin(), val.end(), p.first + 1) - val.begin();
          int r = lower_bound(idx.begin(), idx.end(), p.second) - idx.begin();
          seg.add(l, r, -1);
          q.push(make_pair(l, r));
          continue;
        }

        if (*lower_bound(val.begin(), val.end(), p.first) == p.first) {
          int index = lower_bound(val.begin(), val.end(), p.first) - val.begin();
          seg.add(index, index + 1, -1);
        }
        int l = lower_bound(val.begin(), val.end(), p.first + 1) - val.begin();
        int r = lower_bound(idx.begin(), idx.end(), p.second) - idx.begin();
        seg.add(l, r, -2);
      }

      int l = lower_bound(val.begin(), val.end(), a[i]) - val.begin();
      int r = lower_bound(idx.begin(), idx.end(), i) - idx.begin();
      ans = min(ans, inversion - seg.query(l, r));

      while (!q.empty()) {
        seg.add(q.front().first, q.front().second, -1);
        q.pop();
      }
    }
    if (top[i]) {
      // cerr << i << " is top." << endl;
    }
  }

  cout << ans << endl;
}



Measured memory_bytes: 9408