OMC060(D)

点数: 600

Writer: jun2nosimobe

　$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)$ を求めてください.