As Gerry points out, the sequence $$a_n = [n e] - [(n-1)e],$$$$ a_n = [n e] - [(n-1)e], $$ where $[x]$ is the integer closest to $x$, has the desired extremal property. Unfortunately, one needs to know the value of $e$ to calculate the sequence in this way.
Fortunately, this is a typical example of a Sturmian sequence (on the alphabet $\{2,3\}$), and they can be generated quickly from the continued fraction expansion (of $e$, in this case). If one uses the floor function in place of rounding, this has already been worked out by Ken Stolarsky and Tom Brown, and you can find a simple proof in my article this articleFraenkel's Partition and Brown's Decomposition, which was published in Integerspublished in Integers (pdf). This gives you quickly a large initial segment of the sequence; you cannot jump directly to $a_{1000000}$.
I haven't seen any detailed exposition using the "round" function (or ceiling function), but presumably it follows from the same principles.
A putman-ish followup question is to find a combinatorial process that generates a sequence $b_n$ with $\frac 1n \sum_{i=1}^n b_i \to e$. I don't have an answer for that. Yet.