Guess the Data Structure

Given a series of operations on a black box that supports only two types of operations: insertion and removal, determine which data structure the black box may be mimicking. The possible data structures are:

• Queue: The first inserted element is removed first (FIFO).
• Stack: The last inserted element is removed first (LIFO).
• Max Heap: The largest element is removed first (if there are duplicates, only one is removed).
• Min Heap: The smallest element is removed first (if there are duplicates, only one is removed).

The input begins with an integer \(n\) representing the number of operations. Each of the following \(n\) lines contains two integers. The first integer specifies the type of operation:

1. If the operation is 1, the second integer \(x\) is inserted into the black box.
2. If the operation is 2, the second integer \(y\) is expected to be removed from the black box.

Your task is to simulate the operations for all four candidate data structures. Then:

• If exactly one candidate is possible, output its name: "queue", "stack", "max heap", or "min heap".
• If more than one candidate is possible, output "not sure".
• If none are possible, output "impossible".</p>

  For any variable appearing in a formula, use LaTeX format (for example, \(n\) for the number of operations).

  inputFormat

  The first line contains an integer \(n\) (\(1 \leq n \leq 1000\)), representing the number of operations performed.

  Each of the next \(n\) lines contains two space-separated integers. The first integer is the operation code (either 1 or 2). For an insertion (code 1), the second integer \(x\) is the number to insert. For a removal (code 2), the second integer \(y\) is the number expected to be removed.

  outputFormat

  Output a single line containing one of the following strings:

  • "queue"
  • "stack"
  • "max heap"
  • "min heap"
  • "not sure"
  • "impossible"

  sample

  4
  1 1
  1 3
  1 2
  2 3

  max heap