jmc

By AM-GM, $$\frac{a_k+k}{2}\ge \sqrt{k{a}_k}$$for $1\le k\le 6,$ so $$\begin{array}{rl}\frac{a_1+1}{2}\cdot \frac{a_2+2}{2}\cdot \frac{a_3+3}{2}\cdot \frac{a_4+4}{2}\cdot \frac{a_5+5}{2}\cdot \frac{a_6+6}{2}& \ge \sqrt{a_1}\cdot \sqrt{2a_2}\cdot \sqrt{3a_3}\cdot \sqrt{4a_4}\cdot \sqrt{5a_5}\cdot \sqrt{6a_6}\\ & =\sqrt{6!a_1{a}_2{a}_3{a}_4{a}_5{a}_6}\\ & =6!.\end{array}$$Equality occurs if and only if $a_k=k$ for all $1\le k\le 6.$ Thus, all $6!=720$ permutations satisfy the inequality $$\frac{a_1+1}{2}\cdot \frac{a_2+2}{2}\cdot \frac{a_3+3}{2}\cdot \frac{a_4+4}{2}\cdot \frac{a_5+5}{2}\cdot \frac{a_6+6}{2}>6!,$$except for the permutation where $a_k=k$ for all $1\le k\le 6,$ giving us $720-1=\boxed{719}$ possible permutations.