Solution:
We prove that the number of possibilities is the $n^{\text{th}}$ Fibonacci number $F_{n}$ by induction $\left(F_{0}=1, F_{1}=1\right)$. For the base case, observe that there is 1 way to do it for $n=1$ and 2 ways for $n=2$ (all the arrangements work in both cases).

Now suppose this holds true up to $n-1$ and now consider the arrangements for $n$. Where can we place $n$ in the sequence? Clearly, it can always go in the final position and placing the rest of the numbers is doable in $F_{n-1}$ ways. If it goes in the penultimate position, then the last number must be $n-1$ (since no other number $k$ would satisfy $n(n-1) \leq k n$) and placing the rest is doable in $F_{n-2}$ ways. We now prove $n$ cannot go anywhere else.

Let us place $n$ as $a_{k}$, $k < n-1$. Now consider the smallest element of $a_{k+1}, \ldots, a_{n}$. This element is at most $k$ and so must go in the last position (as it will not satisfy the inequality if it is placed any earlier.) However, we now cannot place anyone in the penultimate position, as the smallest number that can go there is $k+1$ but $(k+1)(n-1) > k n$. You can also obtain a contradiction by trying to place $n-1$, as the earliest it can appear is as $a_{k+1}$.

Solution:
We prove that the problem is strictly equivalent to writing $n$ as a sum of $1$'s and $2$'s, which is a well known recurrence problem left to the reader :)

Consider a permutation that works that is not the identity, and let $i$ be the first index such that $a_{i} \neq i$. It follows that $a_{j}=i$ for some $j>i$. Now, where can we place $j$? If $j$ appears before $a_{j}$, it has to be $a_{i}$, as otherwise the inequality is not satisfied. But if $j \neq i+1$ then we are not able to take any value for $a_{j-1}$, as the smallest number that can go there is $i+1$ but $(i+1)(j-1) > i j$. So either $j=i+1$ and we have swapped around two consecutive terms, or $j$ appears after $a_{j}$. In the latter case, just take the largest value in $a_{i}, a_{i+1}, \ldots, a_{j-1}$. This value is at least $j+1$ but this immediately contradicts the inequality again. In the former case, the placement of $j$ and $j+1$ do not actually affect our ability to place anything afterwards, so we can look at the next index not mapped to itself and conclude it has been swapped with the one immediately following it by the same reasoning, and continue onwards in this manner. Therefore the only changes we can make from the identity permutation are swapping two consecutive values, and this is equivalent to writing $n$ as a sum of $1$'s and $2$'s as desired; a 1 is an element mapped to itself and a 2 is a swap of two consecutive elements.