マージソートツリーを使うと解けます。