#include <iostream>
#include <random>
#include <algorithm>
#include <numeric>
#include <vector>

using namespace std;
using U = uint_fast32_t;
using VU = vector<U>;
using ULA = uint_fast64_t;

enum {
    kLookaheadSize = 64,
};

bool cycleRO(const VU& permutation, size_t i_start, size_t& cnt)
{
    if (i_start == 0)
        return true;

    auto index = i_start;
    do {
        index = permutation[index];
        ++cnt;

        if (index < i_start)
            return false;

    } while (index != i_start);

    return true;
}

void cycleRW(VU& permutation, size_t i_start, ULA& lookahead)
{
    auto index = i_start;
    auto next_ind = permutation[index];

    do {
        const auto value = permutation[next_ind];
        permutation[next_ind] = index;
        index = next_ind;
        next_ind = value;
        const auto lookahead_pos = index - i_start;

        if (lookahead_pos < kLookaheadSize)
            lookahead |= 1ull << lookahead_pos;

    } while (index != i_start);
}

size_t invert(VU& permutation)
{
    size_t cnt = 0;
    const auto n = permutation.size();
    ULA lookahead = 0;

    for (size_t i_start = 0; i_start != n - 1; ++i_start)
    {
        lookahead >>= 1;

        if (!(lookahead&1) && cycleRO(permutation, i_start, cnt))
            cycleRW(permutation, i_start, lookahead);
    }

    return cnt;
}

int main()
{
    random_device rd;
    mt19937_64 rng(rd());

    for (size_t exp = 0; exp <= 20; ++exp)
    {
        const auto n = 1ull << exp;
        VU permutation(n);
        iota(begin(permutation), end(permutation), 0);
        shuffle(begin(permutation), end(permutation), rng);
        VU second_copy(permutation);
        const auto cnt = invert(permutation);
        cout << exp << ' ' << (double)cnt / n << '\n';

        invert(permutation);
        if (permutation != second_copy)
        {
            cout << "Wrong result\n";
            return 0;
        }
    }
}