public class Euler993 {
    private static final long TARGET_N = 1_000_000_000_000_000_000L;
    private static final int CYCLE_START = 512;
    private static final int CYCLE_BANANAS = 71;
    private static final int CYCLE_SHIFT = 118;
    private static final int CHECK_LIMIT = 10_000;

    private static final class Simulator {
        private final int offset;
        private final boolean[] occupied;
        private long x = 0L;
        private int lineCount = 0;

        private Simulator(int maxTarget) {
            offset = 20 * maxTarget + 10_000;
            occupied = new boolean[2 * offset + 10];
        }

        private int index(long position) {
            long idx = position + offset;
            if (idx < 0L || idx >= occupied.length) {
                throw new IllegalStateException("Position outside simulation window: " + position);
            }
            return (int) idx;
        }

        private boolean has(long position) {
            return occupied[index(position)];
        }

        private void set(long position) {
            int idx = index(position);
            if (occupied[idx]) {
                throw new IllegalStateException("Cell already occupied: " + position);
            }
            occupied[idx] = true;
            lineCount += 1;
        }

        private void clear(long position) {
            int idx = index(position);
            if (!occupied[idx]) {
                throw new IllegalStateException("Cell already empty: " + position);
            }
            occupied[idx] = false;
            lineCount -= 1;
        }

        private long[] firstPositions(int maxTarget) {
            long[] first = new long[maxTarget + 1];
            int filled = -1;

            while (filled < maxTarget) {
                boolean here = has(x);
                boolean next = has(x + 1);

                if (here && next) {
                    clear(x + 1);
                    x -= 1;
                } else if (here) {
                    clear(x);
                    x += 2;
                } else if (next) {
                    clear(x + 1);
                    set(x);
                    x += 2;
                } else {
                    int stop = Math.min(lineCount, maxTarget);
                    while (filled < stop) {
                        filled += 1;
                        first[filled] = x;
                    }

                    if (has(x - 1) || has(x) || has(x + 1)) {
                        throw new IllegalStateException("Drop cells are not empty");
                    }
                    set(x - 1);
                    set(x);
                    set(x + 1);
                    x -= 2;
                }
            }

            return first;
        }
    }

    private static long bb(long n, long[] first) {
        long target = n <= 2L ? 0L : n - 2L;
        if (target < first.length) {
            return first[(int) target];
        }

        long cycles = (target - CYCLE_START) / CYCLE_BANANAS;
        int residue = CYCLE_START + (int) ((target - CYCLE_START) % CYCLE_BANANAS);
        return first[residue] + cycles * CYCLE_SHIFT;
    }

    private static void require(boolean condition, String message) {
        if (!condition) {
            throw new IllegalStateException(message);
        }
    }

    private static void runCheckpoints(long[] first) {
        require(bb(0L, first) == 0L, "Checkpoint failed for BB(0)");
        require(bb(1L, first) == 0L, "Checkpoint failed for BB(1)");
        require(bb(2L, first) == 0L, "Checkpoint failed for BB(2)");
        require(bb(3L, first) == 1L, "Checkpoint failed for BB(3)");
        require(bb(5L, first) == -1L, "Checkpoint failed for BB(5)");
        require(bb(1000L, first) == 1499L, "Checkpoint failed for BB(1000)");

        for (int m = CYCLE_START; m + CYCLE_BANANAS <= CHECK_LIMIT; ++m) {
            require(first[m + CYCLE_BANANAS] == first[m] + CYCLE_SHIFT, "Cycle checkpoint failed at " + m);
        }
    }

    public static void main(String[] args) {
        boolean shouldRunCheckpoints = true;

        for (String arg : args) {
            if ("--skip-checkpoints".equals(arg)) {
                shouldRunCheckpoints = false;
                continue;
            }
            System.err.println("Unknown argument: " + arg);
            System.exit(1);
        }

        Simulator simulator = new Simulator(CHECK_LIMIT);
        long[] first = simulator.firstPositions(CHECK_LIMIT);

        if (shouldRunCheckpoints) {
            runCheckpoints(first);
        }

        System.out.println(bb(TARGET_N, first));
    }
}