First take the case $p>3$. Take the permutation such that $a_1<...<a_N$ Then the value of the sum is $$\sum_{i=1}^N a_ia_{i+1}$$$$=\sum_{k=1}^{p^n-1} k(k+1)+\sum_{k=1}^{p^{n-1}}-pk(pk-1)-pk(pk+1)+(pk-1)(pk+1)$$$$=\sum_{k=1}^{p^n-1}k^2+\sum_{k=1}^{p^n-1} k-p^2\sum_{k=1}^{p^{n-1}}k^2-\sum_{k=1}^{p^{n-1}}$$$$=\frac{(p^n-1)p^n(2p^n-1)}{6}-p^2\frac{(p^{n-1}-1)p^{n-1}(2p^{n-1}-1)}{6}-p^{n-1}$$$$\equiv -p^{n-1}\pmod{p^n}$$If $p=3$ the same sum is $$\frac{(3^n-1)3^n(2\cdot 3^n-1)}{6}-3^2\frac{(3^{n-1}-1)3^{n-1}(2\cdot 3^{n-1}-1)}{6}-3^{n-1}$$$$=3^{n-1}(\frac{(3^n-1)(2\cdot 3^n-1)}{2}-1)+3^n\frac{(3^{n-1}-1)(2\cdot 3^{n-1}-1)}{2}$$$$\equiv 3^{n-1}(\frac{2\cdot 2}{2}-1)$$$$\equiv 3^{n-1}\pmod{3^n}$$

Gives ELMO 2010 NT5 vibes!! Fix $a_2,.........,a_N$ and denote $$X \equiv \sum_{j=2}^N a_j a_{j+1} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; f(n) \equiv a_1(a_2+a_N)+X \pmod p$$By Hensel's Lemma,$$f(x) \equiv 0 \pmod {p} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\ f(x) \equiv 0 \pmod {p^{n}}$$has an unique solution. Let $X$ be an unique solution of the second equation then $$f(X+p^{n-1} f'(X) z_0) \equiv f(X)+p^{n-1} f'(X) z_0 \equiv p^{n-1} \pmod {p^{n}} $$($z_0=f'^{-1}(X)$) $\blacksquare$

According to the proposer, he actually gave an explicit permutation for which he wanted a proof that it works - but it turned out that much more natural permutations also work, as we see above. The permutation is $u_k = k + \left\lfloor \frac{k}{p-1} \right\rfloor^{*}$, $k=1,2,\ldots,p^{n-1}(p-1)$ where $\lfloor \cdot \rfloor^{*}$ denotes the largest integer strictly less than the argument (it is also featured in the main official solution).