THE PROGRAM MUST BE IN JAVA

1.You should select the most suitable data structures and taking into consideration the

efficiency of the solutions using a particular data structure.

2.You are not supposed to use java libraries. You need to implement your own data

structures to solve the problems.

There is a bag-like data structure, supporting two operations Throw an element x into the bag. Take out an element from the bag Given a sequence of operations with return values, you're going to guess the data structure. It is a stack (Last-In, First-Out), a queue (First-In, First-Out), a priority-queue (Always take out larger elements first) or something else that you can hardly imagine! Input There are several test cases. Each test case begins with a line containing a single integer n (1