Despite being the first (or 0th) problem, this is one of the more difficult ones in the contest. The militants must be arranged such that the last militant with label ~K~ must be placed before ~K+1~. This can be reworded to having militants with labels ~J~ must be after ~J-1~.

Now, let's assume we have ~Q~ spots where ~Q~ is the sum of all militants. The ~Q^\text{th}~ spot must be filled by a militant with the label ~N~. The order of the rest of the militants labeled ~N~ (all ~m_N-1~ of them) do not matter.

Now those familiar with combinatorics will recognize how we can choose to organize all ~m_N-1~ militants however we want, this bringing in the classical question "~N~ choose ~K~". We can repeat this backwards with each group of militants starting with ~N, N-1, N-2, \dots~.

To do this, we can build a Pascal's triangle and query the answer in ~\mathcal O(1)~ time.

Final complexity: ~\mathcal O(N)~