1915. Browser History

Model a browser's history, starting on page home.

visit p go to page p, discarding everything forward of here back k go back up to k pages, print the page you land on forward k go forward up to k pages, print the page you land on current print the current page

back and forward stop at the ends rather than failing, so asking to go back twenty pages from the second one lands on the first.

## What most people try first

A list that only ever grows, plus an index. visit appends and moves the index to the end, back and forward move the index. It passes every test that walks in one direction, and it is wrong, because a visit must invalidate every page ahead of the current position exactly as a real browser does. An appending design will happily go forward into a page the user abandoned.

The second instinct is to make back k repeat a single step k times and discover that k reaches 100000 while the history may hold one page, so the loop has to stop early anyway.

## An array and a cursor, truncated on visit

Hold the pages in order with an index at the current one. A visit discards everything after the cursor, appends, and advances:

start [home] cursor 0 visit a [home a] cursor 1 visit b [home a b] cursor 2 back 1 [home a b] cursor 1 -> a visit c [home a c] cursor 2 -> b is gone forward 1 [home a c] cursor 2 -> c, not b

back k is cursor = max(0, cursor - k) and forward k is cursor = min(last, cursor + k). No page is ever copied.

## Why it is correct

The forward pages are exactly the slots after the cursor, so discarding them is one truncation rather than a search, and after the truncation the cursor is the last valid index, which is why forward immediately after a visit has nowhere to go. Clamping gives the stated behaviour because max and min are the written-out form of "move k steps or stop at the end, whichever comes first", and they never produce an index outside the array.

An equivalent design keeps a back stack and a forward stack and moves one page between them per step, emptying the forward stack on a visit. It agrees with the cursor version on every input, which is a useful check: the truncation and the emptied stack are the same operation.

## The boundary that breaks a careless implementation

Clamping after indexing rather than before. cursor - k reaches -100000, and in C or Java that reads outside the array while in Python a negative index silently wraps round to the newest page, so the bug prints a plausible answer instead of crashing.

The other one is the discard. Visiting after going back twice, which a test does, leaves an abandoned page reachable in any design that merely appends.

## Overflow

Nothing here is summed. cursor + k reaches at most 200000 and cursor - k at least -100000, both far inside a signed 32 bit integer, whose limits are 2147483647 and -2147483648. The quantity to be careful with is the length: compute last as length - 1 on a non-empty history, which it always is because home is there from the start, so last is never -1.

## Cost

O(1) for back, forward and current, and O(1) amortised for visit, since each page is appended once and discarded at most once across the whole run. Total O(q) time and O(q) memory. The judge cannot enforce the per-operation bound, so stepping one page at a time inside back k also passes; at the stated limits that is about 10^10 steps.

Constraints - `1 ≤ q ≤ 100000` - `1 ≤ k ≤ 100000` - Page names are 1 to 20 lowercase English letters or digits.