  We show that for any fixed $\eps>0$, there are numbers $\delta>0$ and $p_0\ge
2$ with the following property: for every prime $p\ge p_0$ and every integer
$N$ such that $p^{1/(4\sqrt{e})+\eps}\le N\le p$, the sequence $1,2,...,N$
contains at least $\delta N$ quadratic non-residues modulo $p$. We use this
result to obtain strong upper bounds on the sizes of the least quadratic
non-residues in Beatty and Piatetski--Shapiro sequences.
