import std.cstream;

/**
 * PQ-Tree は、「Pノード」「Qノード」「リーフ」の三種類のノードからなる
 * 木構造である。リーフの並べ方に関する条件を表す。
 *   ・Pノードの子要素は好きな順番で並べてOK
 *   ・Qノードの子要素は、木構造上で並んだ順か、その逆順に並べてOK
 * 例えば
 *   P(1 2 3 4 5)
 * は、12345も13425も25431もどの並び方もOKという条件を表す
 *   Q(1 2 3 4 5)
 * は、12345か54321のどっちかならOKという条件を表す
 *   P(1 2 Q(3 4 5))
 * は、12345, 12543, 13452, 15432, 34512, 54312
 *     21345, 21543, 23451, 25431, 34521, 54321 の12種類の並べ方をあらわす
 *
 * PQTree と、(aとbとcは１箇所にまとまってること)みたいな形の条件が
 * 与えられた時に、元のPQTreeのあらわす条件 + 新しい条件をちょうど満たす
 * ような別の PQTree を構成するアルゴリズムがあるらしい。
 *
 * あるらしいのだけどちょっと調べても詳細が見つからなかったので、
 * 適当にある程度は正しそうなものを実装してみる。
 * でも多分、まちがってると思う。こんなに簡単なら調べればすぐ詳細な
 * アルゴリズムが見つかると思うので、多分ほんとはもっと複雑。
 *
 * 「以下の実装が返す結果はすべて条件を満たす」ようにはなってると思うけど、
 * 「条件を満たす並びがあるときに必ずそれを返せる」かというと微妙。
 *
 * というような微妙な代物です。
 */

class PQTree(T)
{
public:
	this( T[] arr... )
	{
		Leaf[] ls;
		foreach( T t ; arr )
			ls ~= new Leaf(t);
		root = P(ls);
	}

	bool seq( T[] arr... )
	{
		c = null;
		foreach( T t ; arr )
			c[t] = 1;
		try
			root = root.satisfy;
		catch( SatFailure s )
			return false;
		return true;
	}

	void debug_print()
	{
		root.debug_print(0);
	}

	T[] result()
	{
		return root.result;
	}

private:
	// root
	Node root;

	// failure
	static class SatFailure : Exception { this(){super("hoge");} }
	void fail() { throw new SatFailure; }

	// current constraint set
	int[T] c;

	// node type
	//   White: 全ての子孫ノードはcと無関係
	//   Gray : どっちも
	//   Black: 全ての子孫ノードはcと関係
	enum {White, Gray, Black};

private:
	static abstract class Node
	{
		int     type(); //<--ほんとはこれcacheかなにかしないと遅い
		Node satisfy();
		Node[] split();
		T[]   result();
		void debug_print(int d);
	}

	class PNode : Node
	{
	public:
		Node[] children;
		override int type() {
			int w,g,b;
			foreach( Node t ; children )
				switch( t.type ) {
				case White: w++; break;
				case Gray : g++; break;
				case Black: b++; break;
				}
			return g||w&&b ? Gray : w ? White : Black;
		}
		override T[] result() {
			T[] ans;
			foreach( Node t ; children )
				ans ~= t.result;
			return ans;
		}
		override void debug_print(int d) {
			for(int i=0; i!=d; ++i) dout.writeString(" ");
			dout.writeLine("P");
			foreach( Node t ; children )
				t.debug_print(d+1);
		}

		override Node satisfy() {
			Node[] ws, gs, bs;
			foreach( Node t ; children )
				switch( t.type ) {
				case White: ws~=t; break;
				case Gray : gs~=t; if(gs.length>=3) fail; break;
				case Black: bs~=t; break;
				}

			if( gs.length==0 ) return P(ws ~ P(bs));
			if( gs.length==1 ) return P(ws ~ Q(gs[0].split ~ P(bs)));
			if( gs.length==2 ) return P(ws ~ Q(gs[0].split ~ P(bs) ~ gs[1].split.reverse));
		}
		override Node[] split() {
			Node[] ws, gs, bs;
			foreach( Node t ; children )
				switch( t.type ) {
				case White: ws~=t; break;
				case Gray : if(!gs)fail; gs =t.split; break;
				case Black: bs~=t; break;
				}
			return P(ws) ~ gs ~ P(bs);
		}
	}

	class QNode : Node
	{
	public:
		Node[] children;
		override int type() {
			int w,g,b;
			foreach( Node t ; children )
				switch( t.type ) {
				case White: w++; break;
				case Gray : g++; break;
				case Black: b++; break;
				}
			return g||w&&b ? Gray : w ? White : Black;
		}
		override T[] result() {
			T[] ans;
			foreach( Node t ; children )
				ans ~= t.result;
			return ans;
		}
		override void debug_print(int d) {
			for(int i=0; i!=d; ++i) dout.writeString(" ");
			dout.writeLine("Q");
			foreach( Node t ; children )
				t.debug_print(d+1);
		}
		override Node satisfy() {
			Node[] ans;
			int i=0;
			for( ;i<children.length && children[i].type==White; ++i )
				ans ~= children[i];
			if( i<children.length && children[i].type==Gray )
				ans ~= children[i].split, ++i;
			for( ;i<children.length && children[i].type==Black; ++i )
				ans ~= children[i];
			if( i<children.length && children[i].type==Gray )
				ans ~= children[i].split.reverse, ++i;
			for( ;i<children.length && children[i].type==White; ++i )
				ans ~= children[i];
			if( i!=children.length )
				fail;
			return Q(ans);
		}
		override Node[] split() {
			if( children[0].type > children[$-1].type )
				children.reverse;
			Node[] ans;
			int i=0;
			for( ;i<children.length && children[i].type==White; ++i )
				ans ~= children[i];
			if( i<children.length && children[i].type==Gray )
				ans ~= children[i].split, ++i;
			for( ;i<children.length && children[i].type==Black; ++i )
				ans ~= children[i];
			if( i!=children.length )
				fail;
			return ans;
		}
	}

	class Leaf : Node
	{
	public:
		T elem;
		this(T e) { elem=e; }
		override int type() { return elem in c ? Black : White; }
		override T[] result() {
			T[] ans;
			ans ~= elem;
			return ans;
		}
		override void debug_print(int d) {
			for(int i=0; i!=d; ++i) dout.writeString(" ");
			dout.writefln(elem);
		}
		override Node satisfy() { return this; }
		override Node[] split() { assert(0); }
	}

	Node P( Node[] ns ) {
		if( ns.length == 1 )
			return ns[0];
		PNode p = new PNode; p.children = ns; return p;
	}

	Node Q( Node[] ns ) {
		if( ns.length == 1 )
			return ns[0];
		QNode q = new QNode; q.children = ns; return q;
	}
}

int main()
{
	// 12345 の並び替えのうち
	PQTree!(int) x = new PQTree!(int)(1,2,3,4,5);
	x.seq(1,4,5); //145がくっついてて
	x.seq(2,3,4); //234がくっついてて
	x.seq(4,5);   //45がくっついてるもの
	//x.debug_print();
	dout.writefln( x.result ); //15423
	return 0;
}