#include<vector>
long long merge_count(std::vector<int>& a) {
  if(a.size() <= 1) return 0;
  long long cnt = 0;
  std::vector<int> b(a.begin(), a.begin() + a.size() / 2);
  std::vector<int> c(a.begin() + a.size() / 2, a.end());
  cnt += merge_count(b) + merge_count(c);
  int ai = 0, bi = 0, ci = 0;
  while(ai < a.size()) {
    if(bi < b.size() && (ci == c.size() || b[bi] <= c[ci])) {
      a[ai++] = b[bi++];
    } else {
      cnt += a.size() / 2 - bi;
      a[ai++] = c[ci++];
    }
  }
  return cnt;
}
long long inversions(std::vector<int> a) {return merge_count(a);}

#include<algorithm>
#include<vector>
template<typename T, T INF>
class SegmentTree {
 public:
  SegmentTree(int n) : size_(1) {
    while(size_ < n) size_ <<= 1;
    node_.assign(size_ << 1, 0);
    lazy_.assign(size_ << 1, 0);
  }
  T find(int left, int right) {return find(left, right + 1, 1, 0, size_);}
  void add(int left, int right, T value) {add(left, right + 1, value, 1, 0, size_);}
 private:
  inline T merge(T vl, T vr) const {return std::max(vl, vr);}
  inline void propagate(int k) {
    if(k < size_) {
      lazy_.at(left_child(k)) += lazy_.at(k);
      lazy_.at(right_child(k)) += lazy_.at(k);
    }
    node_.at(k) += lazy_.at(k);
    lazy_.at(k) = 0;
  }
  int left_child(int node) const {return node << 1;}
  int right_child(int node) const {return (node << 1) + 1;}
  T find(int a, int b, int k, int l, int r) {
    propagate(k);
    if(b <= l || r <= a) return -INF;
    if(a <= l && r <= b) return node_.at(k) + lazy_.at(k);
    auto vl = find(a, b, left_child(k), l, (l + r) / 2);
    auto vr = find(a, b, right_child(k), (l + r) / 2, r);
    return merge(vl, vr);
  }
  T add(int a, int b, T value, int k, int l, int r) {
    propagate(k);
    if(b <= l || r <= a) return node_.at(k);
    if(a <= l && r <= b) return node_.at(k) + (lazy_.at(k) += value);
    auto vl = add(a, b, value, left_child(k), l, (l + r) / 2);
    auto vr = add(a, b, value, right_child(k), (l + r) / 2, r);
    return node_.at(k) = merge(vl, vr);
  }
  int size_;
  std::vector<T> node_;
  std::vector<T> lazy_;
};

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

struct Point {
  int x, y;
  Point(int x, int y): x(x), y(y) {}
};

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for(auto& i: A) cin >> i;

  long long INIT = inversions(A);
  if(INIT == 0) {
    cout << (set<int>(begin(A), end(A)).size() == N ? 1 : 0) << endl;
    return 0;
  }

  enum COLOR {GREY, RED, BLUE};
  vector<COLOR> color(N, GREY);
  int l = 1e9+1, h = -1;
  for(int i = 0; i < N; ++i) {
    if(h < A[i]) color[i] = RED;
    h = max(h, A[i]);
  }
  for(int i = N-1; 0 <= i; --i) {
    if(A[i] < l) color[i] = BLUE;
    l = min(l, A[i]);
  }

  vector<Point> red, blue;
  list<Point> grey;
  for(int i = 0; i < N; ++i) {
    if(color[i] == RED) red.emplace_back(i, A[i]);
    if(color[i] == BLUE) blue.emplace_back(i, A[i]);
    if(color[i] == GREY) grey.emplace_back(i, A[i]);
  }

  long long ans = INIT;
  set<Point, function<bool(Point, Point)>> inside([](Point lhs, Point rhs) {return lhs.y!=rhs.y ? lhs.y<rhs.y : lhs.x<rhs.x;});
  SegmentTree<long long, (long long) 1e18> score(red.size());
  for(auto b: blue) {
    // in
    while(!grey.empty() && grey.front().x < b.x) {
      int l = upper_bound(begin(red), end(red), grey.front().y, [](auto v, auto p) {return v < p.y;}) - begin(red);
      int r = upper_bound(begin(red), end(red), grey.front().x, [](auto v, auto p) {return v < p.x;}) - begin(red) - 1;
      score.add(l, r, 2);
      int ll = lower_bound(begin(red), end(red), grey.front().y, [](auto p, auto v) {return p.y < v;}) - begin(red);
      int rr = upper_bound(begin(red), end(red), grey.front().y, [](auto v, auto p) {return v < p.y;}) - begin(red) - 1;
      if(red[ll].y == grey.front().y) score.add(ll, rr, 1);
      inside.insert(grey.front());
      grey.pop_front();
    }
    // out
    while(!inside.empty() && begin(inside)->y < b.y) {
      int l = upper_bound(begin(red), end(red), begin(inside)->y, [](auto v, auto p) {return v < p.y;}) - begin(red);
      int r = upper_bound(begin(red), end(red), begin(inside)->x, [](auto v, auto p) {return v < p.x;}) - begin(red) - 1;
      score.add(l, r, -2);
      int ll = lower_bound(begin(red), end(red), begin(inside)->y, [](auto p, auto v) {return p.y < v;}) - begin(red);
      int rr = upper_bound(begin(red), end(red), begin(inside)->y, [](auto v, auto p) {return v < p.y;}) - begin(red) - 1;
      if(red[ll].y == begin(inside)->y) score.add(ll, rr, -1);
      inside.erase(begin(inside));
    }
    // g.y == b.y
    for(auto g = begin(inside); g->y == b.y; ++g) {
      int l = upper_bound(begin(red), end(red), g->y, [](auto v, auto p) {return v < p.y;}) - begin(red);
      int r = upper_bound(begin(red), end(red), g->x, [](auto v, auto p) {return v < p.x;}) - begin(red) - 1;
      score.add(l, r, -1);
    }
    // update
    ans = min(ans, INIT - score.find(0, red.size()-1) - 1);
    // g.y == b.y
    for(auto g = begin(inside); g->y == b.y; ++g) {
      int l = upper_bound(begin(red), end(red), g->y, [](auto v, auto p) {return v < p.y;}) - begin(red);
      int r = upper_bound(begin(red), end(red), g->x, [](auto v, auto p) {return v < p.x;}) - begin(red) - 1;
      score.add(l, r, 1);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 8552