n^2よりもっと小さい下界がありそう
でもオーダー的には改善してなさそう