For small $n$ your construction is not optimal (e.g. for $n=6$ there is a group of size 120, isomorphic to $S_5$; $M_{12}$) is an example for $n=12$, the biggest exceptional $n$, it seems).

But for sufficiently large $n$, your construction looks optimal. A way to prove this might go as follows:

• prove that this is the best possible with intransitive groups
• same for imprimitive groups
• for primitive groups, invoke O'Nan-Scott theorem (eventually, the classification of finite simple groups).

Perhaps there is a better way to deal with the last step, I don't know.

For small $n$ your construction is not optimal (e.g. for $n=6$ there is a group of size 120, isomorphic to $S_5$; $M_{12}$) is an example for $n=12$, the biggest exceptional $n$, it seems).

But for sufficiently large $n$, your construction is almost optimal; you can still add an extra 2 to the order of your group. Namely, add the permutation $(1,n/2+1)(2,n/2+2)\dots (n/2,n)$. A way to prove that this becomes optimal (for sufficiently large $n$) might go as follows:

• prove that this is the best possible with intransitive groups
• same for imprimitive groups
• for primitive groups, invoke O'Nan-Scott theorem (eventually, the classification of finite simple groups).

Perhaps there is a better way to deal with the last step, I don't know.