You can divide the $p_i$ into components of successive positives and negatives. Then based on the first residue in the component you can figure out its size by expressing $n=am+b$ and casework on $a,b$. This lets us find the number of positives/negatives in terms of $a$ and $b$. Since you can also find the number of decreasing pairs between two components in terms of their first elements. These two expressions in terms of $a$, $b$, and first elements of components seem to coincide after some algebra. If someone wants to give this approach a go and write up a full solution I'd like to see it, but I just can't bother grinding it out myself.

In complex numbers, setting $\omega$ to be the m-th primitive root and $f(i) = \omega^i+\frac{1}{\omega^i}$ transforms the two conditions into $f(j)\ge f(i)$ and $f(a+b)\ge f(a-b)$ for $a\ge b$,$j\ge i$ in $[1,k]$. Now if $i\equiv j \pmod{2}$ we clearly have the same number of solutions and for the other case note that $\overline{f(j)}\ge f(i)$ and we again are done.