Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Designing a Data Structure

By emrul_mu · Limits 1s, 512 MB

Data structure is one of your favourite topics, isn’t it? Let’s design a new data structure!

In this new data structure, there will be a list and some operations. The operations are :

  • Insert Front X — Insert X into the front of the list.
  • Insert Back X — Insert X into the back of the list.
  • Erase Front — Erase the first element of the list.
  • Erase Back — Erase the last element of the list.
  • Get Front — Print the first element of the list.
  • Get Back — Print the last element of the list.
  • Get Max — Print the maximum element of the list.
  • Get Min — Print the minimum element of the list.

You need to design a data structure as described above and perform Q operations.

Input

The first line of the input will contain a single integer Q, denoting the number of operation.

The next Q lines will contain any of those operations described above.

Constraints

1 ≤ Q ≤ 10^5
1 ≤ X ≤ 10^6

Output

Perform each operation as described in the problem statement.

Samples

InputOutput
8
Insert Back 8
Get Front
Insert Front 9
Get Max
Erase Back
Insert Back 3
Get Back
Get Min
8
9
3
3

Assume that, every operation will be valid.

Discussion