The Tower of Ancient Stones

View as PDF

Submit solution

All submissions

Best submissions

Points: 7

Time limit: 2.0s

Memory limit: 64M

Authors:

sankalp, sahruchi

Problem type

The Tower of Ancient Stones

Blocks arrive one at a time. A block is placed on the tower only if it is strictly smaller than the current top block (the first block always goes on).
Otherwise it is added to the discard pile.Output the discard pile contents in first-discarded to last-discarded order.
If the pile is empty, output EMPTY DISCARD.

Your Task

Given $N$ ~N~ blocks arriving in a specified order, simulate the tower placement rule and output the discard pile.

Input Specification

The first line contains $T$ ~T~ — the number of simulations. Each simulation starts with $N$ ~N~ on its own line, followed by $N$ ~N~ space-separated integers (block values in arrival order).

Output Specification

For each simulation print the discarded values space-separated, or EMPTY DISCARD.

Sample Input

Sample Output

4 2 5
EMPTY DISCARD

Constraints

$1\le T \le 100\,000$ ~1\le T \le 100\,000~
$1 \le N \le 10\,000$ ~1 \le N \le 10\,000~
All block values are distinct positive integers.

Test cases available here!

Comments

0

LightSpeed22 commented on May 31, 2026, 11:20 p.m.

what if the numbers are the same in the input?

0

sankalp commented on June 1, 2026, 12:13 a.m.

Look at 2nd line of the problem statement, it may answer this.

A block is placed on the tower only if it is strictly smaller than the current top block ...

1

LightSpeed48 commented on May 27, 2026, 5:04 a.m.

by far the hardest one of the original 6 problems

1

sankalp commented on May 27, 2026, 10:52 a.m.

then you should check out the new problem Oracle Prophecy Counts... :-)