My solution, it is not Dct.

Induction,...there are1,2,3,...k.fk=(2k-1)!!,let me see n=k+1,

2,3,...k+1,there are n=k,we have fk=(2k-1)!!,How about 1,2,3,...k+1,1 can near any i,put L or R,plus the first L,there are 2k+1,so we have (2k+1)!!.