　左から $k$ 番目の箱を $B_k$ で表す. また, 
$$\begin{aligned}
c_k=\begin{cases}
k&(k\leq n)\\\\
2n+1-k&(k\gt n)
\end{cases}
\end{aligned}$$
と定める. $B_k$ に入っている球に $\sum^{k-1}\_{i=1}c_i+1$ 以上 $\sum^{k}\_{i=1}c_i$ 以下の整数を一つずつ書き込む. このとき, $n(n+1)$ 以下の正の整数が $1$ つずつ書き込まれることになる. ここで, $a=1,2,\dots,n+1$ について, $an$ の書かれた球が初め $B_{l_a}$ に入っているとする. すなわち $l_a$ は $c_1+\cdots+c\_{l_a}\geq an$ となる最小の正の整数である. \
　操作は同じ箱のどの球を取り出しても同じであるから, 箱の中にある一番大きな数が書かれた球を移すとしてよい. このとき, $s\lt t$ なる整数 $s,t$ について, $s$ が書かれた球が $t$ が書かれた球よりも右の箱に入ることはない. \
　$(a-1)n\lt s\leq an$ なる整数 $s$ が書かれた球に注目する. この球の最終的な行き先を $B_{L(s)}$ とすると, 最終的に $B\_1,B\_2,\dots,B\_{L(s)}$ には $1,2,\dots,s$ が書かれた球がすべて入っており, また入っている球の個数の合計は $n$ の倍数であるから, 特に $an$ 以上である. 一方, $B_1,B_2,\dots,B_{L(s)}$ に入っている球の個数の合計は操作により増加しないから, 初めの状態でも $B_1,B_2,\dots,B_{L(s)}$ に入っている球の個数の合計は $an$ 以上である. よって $L(s)\geq l_a$ を得る.\
　逆に, $(a-1)n+1$ 以上 $an$ 以下の整数が書かれた任意の球が最終的に $B_{l_a}$ に入るように操作を行える.  ここで,
$$\sum^{n(n+1)}\_{s=1}L(s)-\sum^{2n}\_{k=1}kc_k$$
のとり得る最小値が $f(n)$ であるから, これは以下のように表される. 
$$f(n)=n\sum^{n+1}\_{a=1}l\_a-\sum^{2n}\_{k=1}kc_k$$
　いま, $1\leq a\leq n$ について $c_1+\cdots+c_{l_a}\geq an\gt c_1+\cdots+c_{l_a-1}$ より
$$c_{2n-l_a+1}+\cdots+c_{2n}\geq an\gt c_{2n-l_a+2}+\cdots+c_{2n}$$
すなわち
$$c_1+\cdots+c_{2n-l_a}\leq (n+1-a)n\lt c_1+\cdots+c_{2n-l_a+1}$$
であるから, 
- $c_1+\cdots+c_{l_a}=an$ のとき $l_{n+1-a}=2n-l_a$, 
- $c_1+\cdots+c_{l_a}\gt an$ のとき $l_{n+1-a}=2n-l_a+1$

である. したがって $a\lt(n+1)\/2$ のとき, $l_a\lt n$ であるから, 
- $an$ が三角数であるとき $l_a+l_{n+1-a}=2n$, 
- そうでないとき $l_a+l_{n+1-a}=2n+1$

をみたす. 
また, $l_{n+1}=2n$, $n$ が奇数のとき $l_{(n+1)\/2}=n $であるから, $g(n)$ で $an$ が三角数となるような $1\leq a\lt(n+1)\/2$ の個数を表すとすると, 
- $n$ が偶数のとき, 
$$\begin{aligned}
\sum^{n+1}\_{a=1}l_a&=(l_1+l_n)+\cdots+(l_{n\/2}+l_{n\/2+1})+l_{n+1}\\\\
&=\frac{n}{2}(2n+1)+2n-g(n)\\\\
&=\frac{2n^2+5n}{2}-g(n)
\end{aligned}$$
- $n$ が奇数のとき
$$\begin{aligned}
\sum^{n+1}\_{a=1}l_a&=(l_1+l_n)+\cdots+(l_{(n-1)\/2}+l_{(n+3)\/2})+l_{(n+1)\/2}+l_{n+1}\\\\
&=\frac{n-1}{2}(2n+1)+n+2n-g(n)\\\\
&=\frac{2n^2+5n-1}{2}-g(n)
\end{aligned}$$

　以下 $g(n)$ を求めよう. $g(n)$ は $b(b+1)\/2$ が $n$ の倍数となるような整数 $1\leq b\lt n$ の個数と一致する. $b=0$ の場合も許すとして考える. $2n$ を互いに素な正の整数 $c,d$ の積で表せたとすると, 中国剰余定理より $c\mid b$ かつ $d\mid(b+1)$ となるような整数 $0\leq b\lt2n$ がただ一つ存在する. これは $d\mid(2n-b-1)$ かつ $c\mid(2n-b)$ と同値である. $b,2n-b-1$ のうちちょうど一方が $0$ 以上 $n$ 未満であるから, それを $b^\prime$ とすると, $2n\mid b^\prime(b^\prime+1)$ となる. \
　逆に, 整数 $b$ が $2n\mid b(b+1)$ をみたすならば, ある互いに素な正の整数 $c,d$ であって, $2n=cd$ かつ $c\mid b$ かつ $d\mid (b+1)$ なるものが存在し, かつ一意であることが容易にわかる. \
　よって, $2n\mid b(b+1)$ となる整数 $0\leq b\lt n$ と, $2n=cd$ なる互いに素な整数 $c,d$ ($c\lt d$) の組は一対一に対応する. したがって $2n$ の素因数の個数 (重複は数えない) を $p(n)$ とすれば, $g(n)=2^{p(n)-1}-1$ である. \
　以上の議論をまとめると, $n$ を $2$ で割った余りを $r$ とするとき, 
$$\begin{aligned}
f(n)&=n\sum_{a=1}^{n+1}l_a-\sum_{k=1}^{2n}kc_k\\\\
&=n\left(\frac{2n^2+5n-r}{2}-(2^{p(n)-1}-1)\right)-\frac{n(n+1)(2n+1)}{2}\\\\
&=n\left(n+\frac{1-r}{2}-2^{p(n)-1}\right)
\end{aligned}$$
となる. 特に, $p(10^6-1)=p(3^3\cdot 7\cdot 11\cdot 13\cdot 37)=6,\ p(10^6)=p(2^6\cdot 5^6)=2$ であるから, 
$$\begin{aligned}
f(10^6-1)+f(10^6)&=(10^6-1)(10^6-33)+10^6(10^6-3\/2)\\\\
&=2\cdot 10^{12}-\frac{71}{2}\cdot 10^6+33\\\\
&=\textbf{1999964500033}
\end{aligned}$$
公式解説
https://onlinemathcontest.com/contests/omc060/editorial/273
　$2n$ 個の箱が左右一列に並んでおり, 初め左から $k$ 番目の箱には, $k\leq n$ のとき $k$ 個, $k\gt n$ のとき $2n+1-k$ 個の球が入っています ($k=1,2,\ldots,2n$).  これらに対し, 
- 一番右以外の箱に入った球を一つ選び, それを箱から取り出し, その箱の一つ右の箱に移す.

という操作を繰り返します. どの箱にも球が $n$ の倍数個入っているようにするために必要な最小の操作の回数を $f(n)$ とします. ただし, この操作を有限回繰り返してそのような状態にできることが保証されます.\
　このとき, $f(10^6-1)+f(10^6)$ を求めてください.