D - Hard Counting Problem

Alice had an array $A$ of $N$ elements, but for no reason whatsoever, a monster has started attacking the array. (Why? How? We don't know either!) The monster does not like non-fixed indices (where a fixed index means that $A_i = i$). Thus, every second starting from $1$, the monster deletes all elements simultaneously from the array at indices $i$ satisfying $A_i \ne i$. The remaining elements