#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
namespace input {
template <class T>
inline void _R(T& x) {
  cin >> x;
}
inline void R() {}
template <class T1, class... T2>
inline void R(T1& x, T2&... y) {
  _R(x);
  R(y...);
}
}  // namespace input
using namespace input;
namespace overload_output {
template <class T1, class T2>
inline ostream& operator<<(ostream& out, pair<T1, T2>& p) {
  return out << p.first << ' ' << p.second;
}
template <class T>
inline ostream& operator<<(ostream& out, vector<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, deque<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, forward_list<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, list<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, set<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, multiset<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, unordered_set<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, unordered_multiset<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T1, class T2>
inline ostream& operator<<(ostream& out, map<T1, T2>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T1, class T2>
inline ostream& operator<<(ostream& out, multimap<T1, T2>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T1, class T2>
inline ostream& operator<<(ostream& out, unordered_map<T1, T2>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T1, class T2>
inline ostream& operator<<(ostream& out, unordered_multimap<T1, T2>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
}  // namespace overload_output
using namespace overload_output;
namespace output {
template <class T>
inline void _W(const T& x) {
  cout << x;
}
template <class T1, class T2>
inline void _W(const pair<T1, T2>& p) {
  _W(p.first);
  _W(' ');
  _W(p.second);
}
template <class T>
inline void _W(const vector<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const deque<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const forward_list<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const list<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2, class T3>
inline void _W(const set<T1, T2, T3>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const multiset<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const unordered_set<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const unordered_multiset<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2>
inline void _W(const map<T1, T2>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2>
inline void _W(const multimap<T1, T2>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2>
inline void _W(const unordered_map<T1, T2>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2>
inline void _W(const unordered_multimap<T1, T2>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
inline void W() { cout << '\n'; }
template <class T>
inline void W(const T& x) {
  _W(x);
  W();
}
template <class T1, class... T2>
inline void W(const T1& x, const T2&... y) {
  _W(x);
  _W(' ');
  W(y...);
}
}  // namespace output
using namespace output;
int main() {
  int n;
  R(n);
  vector<int> v(n);
  for (auto& i : v) R(i);
  int cnt = 0;
  for (int i = 0; i < n - 1; i++)
    for (int j = i + 1; j < n; j++)
      if (v[i] > v[j]) cnt++;
  W(cnt * 2 - cnt % 2);
  return 0;
}
static auto _batch_ios = []() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(12);
  return 42;
}();

### Prompt

Your task is to create a Cpp solution to the following problem:

Jeff has become friends with Furik. Now these two are going to play one quite amusing game.

At the beginning of the game Jeff takes a piece of paper and writes down a permutation consisting of n numbers: p1, p2, ..., pn. Then the guys take turns to make moves, Jeff moves first. During his move, Jeff chooses two adjacent permutation elements and then the boy swaps them. During his move, Furic tosses a coin and if the coin shows "heads" he chooses a random pair of adjacent elements with indexes i and i + 1, for which an inequality pi > pi + 1 holds, and swaps them. But if the coin shows "tails", Furik chooses a random pair of adjacent elements with indexes i and i + 1, for which the inequality pi < pi + 1 holds, and swaps them. If the coin shows "heads" or "tails" and Furik has multiple ways of adjacent pairs to take, then he uniformly takes one of the pairs. If Furik doesn't have any pair to take, he tosses a coin one more time. The game ends when the permutation is sorted in the increasing order.

Jeff wants the game to finish as quickly as possible (that is, he wants both players to make as few moves as possible). Help Jeff find the minimum mathematical expectation of the number of moves in the game if he moves optimally well.

You can consider that the coin shows the heads (or tails) with the probability of 50 percent.

Input

The first line contains integer n (1 ≤ n ≤ 3000). The next line contains n distinct integers p1, p2, ..., pn (1 ≤ pi ≤ n) — the permutation p. The numbers are separated by spaces.

Output

In a single line print a single real value — the answer to the problem. The answer will be considered correct if the absolute or relative error doesn't exceed 10 - 6.

Examples

Input

2
1 2


Output

0.000000


Input

5
3 5 2 4 1


Output

13.000000

Note

In the first test the sequence is already sorted, so the answer is 0.

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
namespace input {
template <class T>
inline void _R(T& x) {
  cin >> x;
}
inline void R() {}
template <class T1, class... T2>
inline void R(T1& x, T2&... y) {
  _R(x);
  R(y...);
}
}  // namespace input
using namespace input;
namespace overload_output {
template <class T1, class T2>
inline ostream& operator<<(ostream& out, pair<T1, T2>& p) {
  return out << p.first << ' ' << p.second;
}
template <class T>
inline ostream& operator<<(ostream& out, vector<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, deque<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, forward_list<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, list<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, set<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, multiset<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, unordered_set<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, unordered_multiset<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T1, class T2>
inline ostream& operator<<(ostream& out, map<T1, T2>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T1, class T2>
inline ostream& operator<<(ostream& out, multimap<T1, T2>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T1, class T2>
inline ostream& operator<<(ostream& out, unordered_map<T1, T2>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T1, class T2>
inline ostream& operator<<(ostream& out, unordered_multimap<T1, T2>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
}  // namespace overload_output
using namespace overload_output;
namespace output {
template <class T>
inline void _W(const T& x) {
  cout << x;
}
template <class T1, class T2>
inline void _W(const pair<T1, T2>& p) {
  _W(p.first);
  _W(' ');
  _W(p.second);
}
template <class T>
inline void _W(const vector<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const deque<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const forward_list<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const list<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2, class T3>
inline void _W(const set<T1, T2, T3>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const multiset<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const unordered_set<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const unordered_multiset<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2>
inline void _W(const map<T1, T2>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2>
inline void _W(const multimap<T1, T2>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2>
inline void _W(const unordered_map<T1, T2>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2>
inline void _W(const unordered_multimap<T1, T2>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
inline void W() { cout << '\n'; }
template <class T>
inline void W(const T& x) {
  _W(x);
  W();
}
template <class T1, class... T2>
inline void W(const T1& x, const T2&... y) {
  _W(x);
  _W(' ');
  W(y...);
}
}  // namespace output
using namespace output;
int main() {
  int n;
  R(n);
  vector<int> v(n);
  for (auto& i : v) R(i);
  int cnt = 0;
  for (int i = 0; i < n - 1; i++)
    for (int j = i + 1; j < n; j++)
      if (v[i] > v[j]) cnt++;
  W(cnt * 2 - cnt % 2);
  return 0;
}
static auto _batch_ios = []() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(12);
  return 42;
}();

```