module solution;
// version = IO_FILES;
import std.algorithm;
import std.array;
import std.conv;
import std.format;
import std.math;
import std.range;
import std.stdio;

immutable string PROBLEM_NAME = "shuffle-twice";

immutable int Mult = 1664525;
immutable int Add = 1013904223;

struct LCG
{
	uint state;

	this (uint state_)
	{
		state = state_;
	}

	void next ()
	{
		state = state * Mult + Add;
	}

	int uniform (int range)
	{
		next ();
		return (state * 1L * range) >> 32;
	}
}

immutable int n = 10000;
immutable uint [] mult;
immutable uint [] add;

static this ()
{
	uint multBack = 1;
	uint addBack = 0;
	uint multPow = Mult;
	uint addPow = Add;
	foreach (i; 0..32)
	{
		addBack = addBack * multPow + addPow;
		multBack = multBack * multPow;
		addPow = addPow * multPow + addPow;
		multPow = multPow * multPow;
	}
	assert ((12345U * multBack + addBack) * Mult + Add == 12345U);
	assert ((123456789U * Mult + Add) * multBack + addBack == 123456789U);
	auto mult_ = new uint [n + 1];
	auto add_ = new uint [n + 1];
	mult_[0] = 1;
	add_[0] = 0;
	foreach (i; 0..n)
	{
		add_[i + 1] = add_[i] * multBack + addBack;
		mult_[i + 1] = mult_[i] * multBack;
	}
	mult = mult_.idup;
	add = add_.idup;
}

int [] simulate (uint seed, int [] c)
{
	auto gen = LCG (seed);
	auto a = n.iota.array;

	void shuffle (int [] a)
	{
		foreach (i; 0..n)
		{
			int j = gen.uniform (i + 1);
			swap (a[i], a[j]);
		}
	}

	shuffle (a);
	shuffle (a);

	if (a[] != c[])
	{
		return null;
	}

	shuffle (a);
	return a;
}

struct PQ
{
	uint p;
	uint q;

	this (const uint p_, const uint q_)
	{
		p = p_;
		q = q_;
	}

	int opCmp () (const auto ref PQ that) const
	{
		return this.q - that.q;
	}

	PQ opBinary (string op) (const auto ref PQ that) const
	    if (op == "+" || op == "-")
	{
		PQ res;
		res.p = mixin ("this.p " ~ op ~ " that.p");
		res.q = this.q + that.q;
		return res;
	}

	ref PQ opOpAssign (string op) (const auto ref PQ that)
	    if (op == "+" || op == "-")
	{
		this = mixin ("this " ~ op ~ " that");
		return this;
	}

	PQ opUnary (string op) () const
	    if (op == "-")
	{
		PQ res = this;
		res.p = -res.p;
		return res;
	}

	PQ opBinaryRight (string op) (const int t) const
	    if (op == "*")
	{
		return PQ (t * p, abs (t) * q);
	}

	auto toString () const
	{
		return format ("(%10u, %10u)", p, q);
	}
}

uint [] getSeeds (int pos, int half, int delta, int [] c)
{
	// get all seeds for hypothesis: the path is
	// pos + delta -> pos + half -> pos
	// random (pos + delta, pos + delta) = pos + half
	// random (n + pos + half, pos + half) = pos

	int start = pos + delta;
	int mid = pos + half;
	int step01 = start + 1;
	int step12 = n + mid - start;
	uint total1 = start + 1;
	uint lo1 = cast (uint) ((((mid * 1L) << 32) + total1 - 1) / total1);
	uint hi1 = cast (uint) (((((mid + 1) * 1L) << 32) + total1 - 1) /
	    total1 - 1);
	uint total2 = mid + 1;
	uint lo2 = cast (uint) ((((pos * 1L) << 32) + total2 - 1) / total2);
	uint hi2 = cast (uint) (((((pos + 1) * 1L) << 32) + total2 - 1) /
	    total2 - 1);
	uint cur2 = lo2;
	uint cur1 = cur2 * mult[step12] + add[step12];

	uint x = lo1;
	uint y = hi1;
	uint w = y - x;
	uint s = cur1;
	uint a = mult[step12];

	void sub (ref PQ a, const ref PQ b)
	{
		if (a.p > w)
		{
			uint t = cast (uint) ((cast (long) (a.p) -
			    max (0, cast (int) (w + 1 - b.p))) / b.p);
			a -= t * b;
		}
	}

	auto lo = PQ (y - s, 0);
	auto hi = PQ (s - x, 0);
	auto up = PQ (a, 1);
	auto dn = PQ (-a, 1);

	sub (lo, up);
	sub (hi, dn);
	while (up.p > w || dn.p > w)
	{
		sub (up, dn);
		sub (lo, up);
		sub (dn, up);
		sub (hi, dn);
	}
	assert (up.p + dn.p > w);

	uint [] res;
	auto first = min (lo.q, hi.q);
	cur2 += first;
	cur1 += first * a;
	auto cur = PQ (cur1, cur2);
	while (lo2 <= cur.q && cur.q <= hi2)
	{
		if (x <= cur.p && cur.p <= y)
		{
			uint cur0 = cur.p * mult[step01] + add[step01];
			res ~= cur0;
		}
		if (x <= cur.p - dn.p && cur.p - dn.p <= y)
		{
			cur -= dn;
		}
		else
		{
			cur += up;
		}
	}

	return res;
}

void solve (int [] c)
{
	bool [uint] seeds;
	foreach_reverse (pos; 0..n)
	{
		auto delta = c[pos] - pos;
		foreach (half; 0..delta + 1)
		{
			auto addSeeds = getSeeds (pos, half, delta, c);
			foreach (seed; addSeeds)
			{
				if (seed in seeds)
				{
					auto a = simulate (seed, c);
					if (a !is null)
					{
						a[] += 1;
						writefln ("%(%s %)", a);
						return;
					}
				}
				else
				{
					seeds[seed] = true;
				}
			}
		}
	}
	assert (false);
}

void main (string [] args)
{
	version (IO_FILES)
	{
		stdin  = File (PROBLEM_NAME ~ ".in",  "rt");
		stdout = File (PROBLEM_NAME ~ ".out", "wt");
	}

	int cn;
	while (readf (" %s", &cn) > 0)
	{
		assert (cn == n);
		readln;
		auto c = readln.split.map !(to !(int)).array;
		c[] -= 1;
		solve (c);
	}
}