E=enumerate
L=len
def f(l,I=[],r=[]):
 if L(I)==L(l):yield r;return
 for i,a in E(l):
  if(i in I)<a==1:
   j,k,Q,W=i,i,[],[]
   while(j:=j-1)>=0==(j in I)and~-l[j]*(Q==[]or Q[-1][0]<l[j]):Q+=(l[j],j),
   while(k:=k+1)<L(l)and~-(k in I)*~-l[k]*(W==[]or W[-1][0]<l[k]):W+=(l[k],k),
   for x in range((A:=max(L(Q),L(W)))*A):
    for o,V in E(u:=[Q[:x//A+1],W[:x%A+1]]):
     if V and V[0][0]==2:
      M=V+u[1>o]
      if L(S:=[X for X,_ in M])==L({*S}):yield from f(l,I+[j for _,j in M]+[i],r+[M+[(a,i)]])
   yield from f(l,I+[i],r+[[(1,i)]])
def F(l):
 R=[];B={str(sorted(j))for j in f(l)}
 for i in map(eval,B):
  v=[-1]*L(l)
  for P,j in E(i):
   for _,I in j:v[I]=P
  R+=v,
 return{*map(tuple,R)}
 
print(F([1,2,1]))
print(F([2,1,3,2,1]))
print(F([1,2,1,2,1]))
print(F([1,6]))
print(F([4,2,3,1]))
print(F([1]))
print(F([1,2,3,4]))
print(F([4,3,1,2]))
print(F([3,1,2,4]))
print(F([1,2,1,3]))
print(F([1,2,2,1]))
print(F([1, 2, 4, 3]))

RT1lbnVtZXJhdGUKTD1sZW4KZGVmIGYobCxJPVtdLHI9W10pOgogaWYgTChJKT09TChsKTp5aWVsZCByO3JldHVybgogZm9yIGksYSBpbiBFKGwpOgogIGlmKGkgaW4gSSk8YT09MToKICAgaixrLFEsVz1pLGksW10sW10KICAgd2hpbGUoajo9ai0xKT49MD09KGogaW4gSSlhbmR+LWxbal0qKFE9PVtdb3IgUVstMV1bMF08bFtqXSk6USs9KGxbal0saiksCiAgIHdoaWxlKGs6PWsrMSk8TChsKWFuZH4tKGsgaW4gSSkqfi1sW2tdKihXPT1bXW9yIFdbLTFdWzBdPGxba10pOlcrPShsW2tdLGspLAogICBmb3IgeCBpbiByYW5nZSgoQTo9bWF4KEwoUSksTChXKSkpKkEpOgogICAgZm9yIG8sViBpbiBFKHU6PVtRWzp4Ly9BKzFdLFdbOnglQSsxXV0pOgogICAgIGlmIFYgYW5kIFZbMF1bMF09PTI6CiAgICAgIE09Vit1WzE+b10KICAgICAgaWYgTChTOj1bWCBmb3IgWCxfIGluIE1dKT09TCh7KlN9KTp5aWVsZCBmcm9tIGYobCxJK1tqIGZvciBfLGogaW4gTV0rW2ldLHIrW00rWyhhLGkpXV0pCiAgIHlpZWxkIGZyb20gZihsLEkrW2ldLHIrW1soMSxpKV1dKQpkZWYgRihsKToKIFI9W107Qj17c3RyKHNvcnRlZChqKSlmb3IgaiBpbiBmKGwpfQogZm9yIGkgaW4gbWFwKGV2YWwsQik6CiAgdj1bLTFdKkwobCkKICBmb3IgUCxqIGluIEUoaSk6CiAgIGZvciBfLEkgaW4gajp2W0ldPVAKICBSKz12LAogcmV0dXJueyptYXAodHVwbGUsUil9CiAKcHJpbnQoRihbMSwyLDFdKSkKcHJpbnQoRihbMiwxLDMsMiwxXSkpCnByaW50KEYoWzEsMiwxLDIsMV0pKQpwcmludChGKFsxLDZdKSkKcHJpbnQoRihbNCwyLDMsMV0pKQpwcmludChGKFsxXSkpCnByaW50KEYoWzEsMiwzLDRdKSkKcHJpbnQoRihbNCwzLDEsMl0pKQpwcmludChGKFszLDEsMiw0XSkpCnByaW50KEYoWzEsMiwxLDNdKSkKcHJpbnQoRihbMSwyLDIsMV0pKQpwcmludChGKFsxLCAyLCA0LCAzXSkp