GreatPower

$1$以上の整数$n$に対して$M^n = M・M^{n-1}$です。従って以下のようなアルゴリズムで答えが求まります。

1. 数列中の最小の値を$M^{A_i}$とする。
2. $\lfloor\frac{数列中に存在するM^{A_i}の個数}{M}\rfloor$個の$M^{A_i+1}$を数列に加える。
3. 数列から$M^{A_i}$をすべて削除する。
4. 数列が空の場合、答えは$A_i$である。そうでない場合は1に戻る。

適切なデータ構造を用いることで$O(NlogN)$などでこの問題を解くことができます。