#include #include using namespace std; vector permute(vector a, vector b) { int n = a.size(); vector ainv(n); for (int i=0; i c(n); for(int i=0; i& a) { if (a.size() == 1) return 0; vector left = vector(a.begin(), a.begin() + a.size() / 2); vector right = vector(a.begin() + a.size() / 2, a.end()); long long swaps = numswaps(left) + numswaps(right); a.clear(); int i=0, j=0; while (i < left.size() && j < right.size()) { if (left[i] < right[j]) { a.push_back(left[i++]); } else { a.push_back(right[j++]); swaps += left.size() - i; } } while (i < left.size()) { a.push_back(left[i++]); } while (j < right.size()) { a.push_back(right[j++]); } return swaps; } int main() { long long n; cin>>n; vector a(n),b(n),c(n); for (int i=0; i>a[i]; for (int i=0; i>b[i]; for (int i=0; i>c[i]; vector ab = permute(a,b); vector ac = permute(a,c); vector bc = permute(b,c); cout << (n*(n-1) - numswaps(ab) - numswaps(ac) - numswaps(bc)) / 2 << endl; return 0; }