For the case $n=3$, take $a_1 = (1,2)$ and $a_2 = (1,3,2)$ instead of 
$a_1 = (1,2,3)$ and $a_2 = (1,2)$.

A major motivation for posting this answer is to give Xueyi Huang an opportunity to exclude this case in one way or another if it is not really relevant.