Observe that the optimal rearranging protocol will be as follows: choose a book numbered ~K~, then put books ~K, K-1, \dots, 2, 1~ (~K~ through ~1~) to the top of the stack. Following is the proof of optimality for such a protocol.

If we put book numbered ~K~ on the top first, then it is certain that we will have to, at a later point, put each book with number less than ~K~ on the top. Otherwise, that book would end up below book ~K~ in the final array.

Similarly, if we previously put book ~K~ on top during our optimal reordering protocol, no other book with a number greater than ~K~ is worth putting on top, because we would have to put book ~K~ on top again (otherwise, book ~K~ would appear below this book in the final array). However, there is no point in moving book ~K~ on top twice, since the first movement could be ignored to get a shorter protocol, which means the former one was not optimal, contrary to the initial assumption. It follows that we should not put any book greater than ~K~ on top.

Therefore, if ~K~ is the number of the book we put on top at the start of an optimal protocol, we must put all books numbered less than ~K~, and no other book. It is now clear that these books must be put in order ~K~ through ~1~.

After these movements, the first ~K~ numbers will be ~1~ through ~K~, so we are interested if the remainder of the array is sorted making numbers ~K+1~ through ~N~ follow. In order for this to be true, all numbers greater than ~K~ must form an increasing subsequence in the original array because, by moving numbers ~1, 2, \dots, K~, the relative ordering of other numbers is preserved, and this should be increasing in the final array.

Thus, we can let ~K~ be any number such that ~K+1, K+2, \dots, N~ form an increasing subsequence in the initial array. Clearly, since we seek a solution with a minimal number of movements, we will choose the smallest ~K~ such that the above conditions hold.

Note that if ~K~ has the above property, then ~K+1~ has this property as well, because if ~K+1, K+2, \dots, N~ form an increasing subsequence, then this is also true for ~K+2, K+3, \dots, N~. Thus, we can find the minimal ~K~ using binary search, or we can look at numbers ~N, N-1, N-2, \dots~ and find the greatest of them which does not form a decreasing subsequence with the previous elements of the array.