OI XXVI - cyk

// https://szkopul.edu.pl/problemset/problem/e86SVYtB-4G3yVTFi2unCZWa/site/?key=statement

#include <bits/stdc++.h>

// #define GARY_DBG
#define GARY_LIB

#include "cyklib.hpp"

constexpr int sizik = 1000 * 1001;

#define ar std::array

typedef std::vector<std::vector<int>> _kra;

#define int int64_t

int count_inv(int a, int b, int c) {
    return (a > b) + (a > c) + (b > c);
}

int f;

int compare(int x, int a) {
    int d = x >> 1;
    int b = circular_shift(d);
    int c = f = circular_shift(d);

    if (a == c) {
        return 0;
    } else if (count_inv(a, b, c) & 1) {
        return 1;
    } else {
        return -1;
    }
}

void solve() {
    int g = f = circular_shift(0);
    f = circular_shift(1);
    if (g == f) {
        give_answer(1);
        return;
    }

    int x = 2;
    int l = 0, r = 0;
    while (true) {
        int c = compare(x, f);
        if (c == 0) {
            give_answer(x);
            return;
        }

        if (c == 1) {
            l = x >> 1, r = x;
            break;
        }

        x *= 2;
    }

    while (r - l > 2) {
        int s = (l + r) / 2;
        if (s & 1) s--;

        int c = compare(s, f);
        if (c == 0) {
            give_answer(s);
            return;
        } else if (c == -1) {
            l = s;
        } else {
            r = s;
        }
    }

    if ((r - l) == 2) {
        give_answer(l + 1);
        return;
    }
}

#undef int

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}