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.

Further edit on April 21:  As anticipated, Xueyi Huang has made a minor modification to the earlier form of the question and this answer is not a valid answer to the current form of the question.