忘れてたけど、文字列の最後の文字aも覚えておく
復元もブロックソートそっくり。