#include <bits/stdc++.h>

using namespace std;
using ull = unsigned long long;

long long Slow(vector<int>& v) {
  int n = v.size();
  vector<vector<bool>> dp(n, vector<bool>(n, false));
  long long ans = 0;
  for (int l = n - 1; l >= 0; --l) {
    for (int r = l + 1; r < n; ++r) {
      dp[l][r] = dp[l + 1][r] ^ dp[l][r - 1] ^ dp[l + 1][r - 1] ^ (v[l] > v[r]);
      ans += dp[l][r];
    }
  }
  return ans;
}

long long Fast(vector<int>& v) {
  int n = v.size();
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  
  // 1. We compute the total number of inversions (mod 2)
  // in O(n log n) using a fenwick tree
  vector<bool> fw(n + 1, false), invs(n, false);
  sort(order.begin(), order.end(), [&](int a, int b) {
    return v[a] > v[b];
  });
  for (auto i : order) {
    for (int j = i + 1; j > 0; j -= (j & -j))
      invs[i] = invs[i] ^ fw[j];
    for (int j = i + 1; j <= n; j += (j & -j))
      fw[j] = fw[j] ^ 1;
  }

  // row_msks[i] = row sum of [l..i] mod 2 for all i in [buck..buck+64)
  // sum[i] = suffix sums over msks[i] as a bitset
  // Invariant: invs[i] = parity of number of inversions (j, i) with buck <= j < i
  vector<ull> row_msks(n);
  vector<int> norder;
  long long total = 0;
  for (int buck = 0; buck < n; buck += 64) {
    norder.clear();
    ull row_msk = 0;
    bool parity = false;
    for (auto i : order) {
      assert(i >= buck);
      if (i < buck + 64) {
        // Here we have amortized n iterations, so we afford to do O(64)
        row_msks[i] = 0;
        for (int j = i - 1; j >= buck; --j) 
          if (v[j] > v[i])
            row_msks[i] ^= (1ULL << (j - buck + 1)) - 1;
        row_msk ^= (i - buck + 1 >= 64 ? 0ULL : (1ULL << (i - buck + 1))) - 1;
        parity = !parity;
      } else {
        row_msks[i] = row_msk;
        invs[i] = invs[i] ^ parity;
        if (invs[i]) row_msks[i] = ~row_msks[i];
        norder.push_back(i);
      }
    }
    for (int i = buck; i < n; ++i) {
      if (i > buck) row_msks[i] ^= row_msks[i - 1];
      total += __builtin_popcountll(row_msks[i]);
    }
    swap(order, norder);
  }
  return total;
}

void TestCorrect() {
  mt19937 rng(52);
  while (true) {
    int n = (rng() % 512) + 1;
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    shuffle(order.begin(), order.end(), rng);
    int S = Slow(order);
    int F = Fast(order);
    if (S == F) {
      cout << "OK n=" << n << " ans=" << S << endl;
      continue;
    }
    cout << "ERROR" << endl;
    cout << n << endl;
    for (auto i : order) cout << i + 1 << " ";
    cout << endl;
    cout << "SLOW=" << S << " FAST=" << F << endl;
    assert(false);
  }
}

void TestBig() {
  mt19937 rng(52);
  int n = 100000;
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  shuffle(order.begin(), order.end(), rng);
  cout << Fast(order) << endl;
}

int main() {
  // TestCorrect();
  TestBig();
  return 0;
}