#define V S v=I[i]
#define D B[i]
#define U return
#define Y(x)if(!B[x].H){B[x].H=1;if(M(I,N,x,Q-1))U 1;B[x].H=0;}
using S=int;struct A{S C;S E;S G;S F;S H;};A B['( '];S M(S I[],S N,S i,S Q){if(!Q)U 1;V;if(D.C)Y(i-v)if(D.E)Y(i+v)U 0;}S T(S I[],S N){S K=0,J=0,i=N,P=1;for(;i--;D.C|D.E?K++:J+=D.F=1){V;D.C=i>=v,D.E=i+v<N;D.G=D.F=D.H=0;}if(J>1)U 0;while(P&&K>0){P=0;for(i=N;i--;){V;!D.F?D.C&&B[i-v].G?D.C=0,P=1:0,D.E&&B[i+v].G?D.E=0,P=1:0,D.C?D.E?:J?B[i-v].G=D.F=P=1:0:D.E?J?B[i+v].G=D.F=P=1:0:J+=D.F=1:0;}if(J>1)U 0;}for(i=N;i--;D.H=0)if(D.H=1,M(I,N,i,N-1))U 1;U 0;}