Subtask 1

We note that with acorns of only sizes 1 and 2, each acorn of size 1 can be nested inside a single acorn of size 2 and each acorn of size 2 cannot be nested in any other acorn. It is always optimal to place an acorn of size 1 inside an acorn of size 2 if they do not already contain an acorn of size 1, since any other acorn that could be nested would also be of size 1.

Time Complexity: ~\mathcal O(N)~

Subtask 2

For full points, we notice that it is optimal to nest as many acorns as possible. By processing the acorns in non-decreasing order, we know that for any acorn of size ~i~, it can be nested in any acorn of at least size ~i+1~.

We also observe that it is optimal for an acorn of size ~i~ to have the largest acorn that is at least as small as size ~i-1~ to be nested inside it.

Thus for every acorn being processed, we can add it to some container, then we can remove the largest acorn that is smaller than the current acorn being processed from the container, if one exists.

Time Complexity: ~\mathcal O(N^2)~ or ~\mathcal O(N \log N)~

Bonus: There's also an ~\mathcal O(N+\max(a_i))~ solution.