If $\{x_n\}$ is a non-decreasing sequence of integers, uniformly "half-distributed" relative to $n$ as $n\to\infty,$ then $\frac{\sum x_n}{n^2}\to 1?$ Let $\{ x_n\}_{n\in\mathbb{N}}$ be a non-decreasing sequence of integers such that
$$ \lim_{n\to\infty} \left( \frac{\text{number of elements in } \{x_i\}_{i\leq n} \text{ that are } \leq n }{n} \right) = \frac{1}{2}. $$
Then does $$ \lim_{n\to\infty} \left( \frac{\sum_{i=1}^n x_i}{n^2} \right) = 1\quad ? $$
The result is true for $\ x_n = 1+2n,$ or $x_n = 2n,$ so I was wondering if the more general result in the question was true, but I'm not sure if the condition is restrictive enough to guarantee the result.
The "non-decreasing" condition is there for otherwise $x_1=1, x_2=1000, x_3=1, x_4=1000000, x_5=1, x_6=1000000000, x_7=1, ...$ would be a counter-example.
 A: We can show that the given conditions imply
$$ \tag{$*$}
\lim_{n \to \infty} \frac{x_n}{2n} = 1 \, ,
$$
and then
$$
\lim_{n\to\infty}  \frac{\sum_{i=1}^n x_i}{n^2}  
= \lim_{n\to\infty} \frac{x_n}{n^2-(n-1)^2} = 1 
$$
follows using the Stolz–Cesàro theorem.

It remains to prove $(*)$. The idea is that among the first $2n$ numbers, about $n$ are $\le 2n$. Since the sequence is non-decreasing, roughly the first $n$ are $\le 2n$ and the next $n$ are $> 2n$. Which means that $x_n$ is approximately $2n$.
Let's now make this rigorous: Given $\epsilon > 0$ there is an $N$ such that
$$
  (1 - \epsilon) \frac{n}{2} < \# \{ 1 \le i \le n \mid x_i \le n \} < (1 + \epsilon) \frac{n}{2} 
$$
for all $n \ge N$. For such a $n$ set $k = \lfloor 2n/(1+\epsilon) \rfloor $ and $l =  \lceil 2n/(1-\epsilon) \rceil $. Then
$$
 \#\{ 1 \le i \le k\mid x_i \le k\} <(1 + \epsilon) \frac{k}{2}  \le n
\implies x_n > k \ge \frac{2n}{1 + \epsilon} - 1
$$
and
$$
 \#\{ 1 \le i \le l \mid x_i \le l\} >(1 - \epsilon) \frac{l}{2}  \ge n
\implies x_n \le  l \le \frac{2n}{1 - \epsilon} +1\, .
$$
Here it is used that the sequence is non-decreasing.
So for any $\epsilon > 0$ there is an index $N$ such that
$$
\frac{1}{1+\epsilon} - \frac{1}{2n} \le \frac{x_n}{2n} \le \frac{1}{1-\epsilon} + \frac{1}{2n}
$$
for all $n \ge N$, and that proves $(*)$.
Remark: This argument works for sequences of real numbers, not only for sequences of integers.

Generalization: In the same way one can prove the following: Let $(x_n)$ be a non-decreasing sequence of real numbers. If
$$
 \lim_{n \to \infty} \frac{\# \{ 1 \le i \le n \mid x_i \le n \}}{n} = \alpha
$$
then
$$
\lim_{n \to \infty} \frac{x_n}{n} = \begin{cases}
\frac{1}{\alpha} & \text{ if } 0 < \alpha \le 1 \, \\
\infty & \text{ if } \alpha = 0 \, .
\end{cases}
$$
