import random

def collisions(perm):
    n = len(perm)
    seen = {}
    bad = 0
    for i in range(n):
        for j in range(i+1, n):
            d = (j - i, perm[j] - perm[i])
            if d in seen:
                bad += 1
            else:
                seen[d] = 1
    return bad

def anneal(n, iters=200000, seed=0):
    rnd = random.Random(seed)
    perm = list(range(1, n+1))
    rnd.shuffle(perm)
    cur = collisions(perm)
    best = cur
    best_perm = perm[:]
    T0, T1 = 5.0, 0.01
    for step in range(iters):
        T = T0 * (T1/T0) ** (step/iters)
        i, j = rnd.randrange(n), rnd.randrange(n)
        if i == j: continue
        perm[i], perm[j] = perm[j], perm[i]
        new = collisions(perm)
        if new <= cur or rnd.random() < pow(2.718281828, (cur-new)/T):
            cur = new
            if cur < best:
                best = cur
                best_perm = perm[:]
                if best == 0:
                    return best_perm, 0
        else:
            perm[i], perm[j] = perm[j], perm[i]
    return best_perm, best