The Lazy Librarian's Stack

Minimum 4 moves. Books D, E, F, G are already in correct relative order (LIS of length 4 from bottom). Move H, C, B, A to the top in that order (4 moves). Final stack top-to-bottom: A, B, C, D, E, F, G, H.

The minimum number of moves equals n minus the length of the longest subsequence of books that are already in sorted order reading from bottom to top of the stack — because those books need never be touched. Step 1: Current stack top-to-bottom: G, C, F, A, H, B, E, D. Bottom-to-top reading: D, E, B, H, A, F, C, G. Step 2: Target order bottom-to-top (alphabetical A at bottom, H at top): A, B, C, D, E, F, G, H. Step 3: Find longest subsequence of (D,E,B,H,A,F,C,G) that is a subsequence of (A,B,C,D,E,F,G,H) and appears in order. This is the Longest Increasing Subsequence (LIS) of the bottom-to-top reading relative to alphabetical order. Step 4: Map each book to its alphabetical rank: D=4, E=5, B=2, H=8, A=1, F=6, C=3, G=7. Sequence: 4,5,2,8,1,6,3,7. Find LIS: 4,5,8 (length 3) or 4,5,6,7 (length 4) or 2,6,7. Yes! LIS length = 4. Step 5: Books in LIS (ranks 4,5,6,7 = D,E,F,G): these 4 books are already in sorted relative order from bottom. They stay in place. Step 6: Books not in LIS: A, B, C, H (4 books). These must be moved to the top. Move them in reverse alphabetical order (so the last moved ends up on top in correct order): move H first, then C, then B, then A. After 4 moves, stack top-to-bottom: A,B,C,D,E,F,G,H. Key Insight: The connection between this stack-sorting problem and the Longest Increasing Subsequence is elegant and non-obvious. The LIS of the bottom-to-top reading (mapped to sorted ranks) identifies exactly which books are already correctly sequenced relative to each other — and those need zero moves. Everything else must be rebuilt from scratch by moving to the top.