We can use the characterization [by Christie][1]. Let $\pi \in S_n$. Add a fixed point $0$ to $\pi$, and let $c$ be the cycle $(0, 1, \ldots, n)$. Then the smallest number of block interchanges to sort $\pi$ is equal to $\frac{n + 1 - t}{2}$, where $t$ is the number of cycles in decomposition of $c \pi^{-1} c^{-1} \pi$. When $n$ is odd, the maximum value is obtained at $t = 2$, and we are counting $\pi$ such that $c \pi^{-1} c^{-1} \pi$ decomposes into two cycles. Note that $\pi^{-1} c^{-1} \pi$ is itself a cycle, and for any cycle $d$ the equation $d = \pi^{-1} c^{-1} \pi$ has a single solution for $\pi$ (under $\pi(0) = 0$).

According to a [result of Zagier][2] (a different presentation [here][3]), the product $cd$ of two random $2n$-cycles $c, d$ decomposes into exactly two cycles with probability $2s_{2n + 1, 2} / (2n + 1)! = 2H_{2n} / (2n + 1)$, where $s_{2n + 1, 2}$ is the Stirling number of the first kind. Since $c$ is fixed, we immediately have $a(2n - 1) = (2n - 1)! \frac{2H_{2n}}{2n + 1} = (2n)! \frac{H_{2n}}{n(2n + 1)}$.

For $a(2n)$ we want to count the number of $(2n + 1)$-cycles $d$ such that $cd$ is a $(2n + 1)$-cycle. Using the same formula, we have an even simpler relation $a(2n) = \frac{(2n)!}{n + 1}$.


  [1]: https://www.sciencedirect.com/science/article/abs/pii/S002001909600155X?via%3Dihub
  [2]: https://people.mpim-bonn.mpg.de/zagier/files/tex/CyclesOfElemsSymmGroups/fulltext.pdf
  [3]: https://www.sciencedirect.com/science/article/pii/S0195669812000510