/*
 * Complete the 'lilysHomework' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts INTEGER_ARRAY arr as parameter.
 */

void _print(const vector<int>& v) {
    for (auto e: v) { cout << e << " "; }
    cout << endl;
}

int _count(vector<int>& rx) {
    int n = rx.size();
    int i = 0;
    int j;
    int count = 0;
    while (i < n) {
        while ((j = rx[i]) != i) {
            swap(rx[i], rx[j]);
            count++;
        }
        i++;
    }
    return count;
}

int lilysHomework(vector<int> arr) {
    int n = arr.size();
    // _print(arr);

    vector<int> ix(n);
    iota(ix.begin(), ix.end(), 0);
    // _print(ix);    
    sort(ix.begin(), ix.end(), [&arr](int i, int j) { return arr[i] < arr[j]; });
    // _print(ix);

    vector<int> rx(n);  // rank
    for (size_t i = 0; i < n; ++i) { rx[ix[i]] = i; }
    // _print(rx);

    vector<int> rrx(n); // reversed rank
    for (size_t i = 0; i < n; ++i) { rrx[i] = n - 1 - rx[i]; }
    // _print(rrx);
    
    int c1 = _count(rx);
    int c2 = _count(rrx);
    
    return min(c1, c2);
}