Consider a sequence A $=($a$1,$ a$2,...,$ an $)$ consisting of distinct positive

integers. Let each element ai of A$,$ where i $=2$k for some positive integer k$,$ be positioned in the

sorted list of A such that it is either $($i$)$ at its sorted position or $($ii$)$ within two positions $($either to

the left or right$)$ from its sorted position.

For example, given a sequence A :$=($a$1,...,$ a$10),$ the possible positions of the element a$2$ in the

sorted list of A can be $1,2,,4$

$(1)$ Derive a formula that calculates the total number of possible sequences for any given n$.$