Tutorial — Stack Element Retrieval Process

Ta nhận xét rằng nếu một đĩa ở vị trí $p$ trong ống ban đầu bị rút ra, toàn bộ các đĩa nằm ở vị trí từ $1$ đến $p$ đều đã bị chuyển vào hộp thu gom.

Do đó, các đĩa chưa bị rút khỏi ống tại bất kỳ thời điểm nào luôn nằm ở các vị trí liên tiếp phía sau vị trí sâu nhất đã từng bị rút ra.

Lưu trước vị trí của từng đĩa trong mảng ban đầu và duy trì biến $max\_pos$ lưu vị trí lớn nhất đã bị rút. Với mỗi $b_i$, nếu $pos[b_i] > max\_pos$, đáp số là $pos[b_i] - max\_pos$ và ta cập nhật $max\_pos = pos[b_i]$; ngược lại đáp số là $0$.