In addition to the character sum approach explained by Charles and Robin, which gives you a precise formula for the number of NRN patterns $\mod p$ for any $p$, in the case $p\equiv 3(\mod 4)$ there is an elementary proof that avoids elliptic curves or Gauss sums. (**Notation:** N is quadratic non-residue, R is quadratic residue.)

I claim that it is sufficient to find an arithmetic progression $\mod p$ of the form $-a^2,1,-b^2$ with non-zero $a,b.$ Indeed, $-a^2$ and $-b^2$ are N and 1 is R. Choose the sign so that $n=\pm(1+a^2)$ is R: this is possible since $-1$ is a quadratic non-residue $(\mod p),$ by the assumption on $p$. Dividing by $n$, we'll get three consecutive non-zero numbers $\mod p$ in pattern NRN. Thus it remains to show that $a^2+b^2=-2 (\mod p)$ has a solution with $a,b\ne 0,$ which is a special case of the well known fact that for $p\geq 7,$ any non-zero element of $\mathbb{Z}/p\mathbb{Z}$ is the sum of two non-zero squares. Conversely, all NRN patterns are obtained in this way and with a tiny bit of extra work, one can count that there are $(p+1)/8$ or $(p-3)/8$ of them, depending on whether $p\equiv 7(\mod 8)$ or $p\equiv 3(\mod 8).$