Practice on Toph

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

Primary Key

Limits: 2s, 512 MB

“Clarity-Lon” is the new awesome e-commerce based startup that went to the top of the chart within few weeks. As their customer number is going up day by day, they kept an electronic board at their office which shows total number of customers they currently have. For maintenance, they used a “Raspberry Pi” which runs query to the database about certain information. As the system is poorly designed they have some problems. Sometimes a lot of people gets registered at the same time and their system gets frozen because of poor query operations. Now you need to optimize the system.

Initially, you have n number of people. You need to answer some queries. Each time, a new customer registered in the system, they are tagged with a primary key or id number. When the company provide offers, the customers who registered earlier gets priority. You know query on a database by time-stamp is not a good idea. On the other hand query, with primary key runs faster on the database.

Here the database ( table ) use auto increment primary key feature. A primary key is a value which identifies a data ( row ) uniquely in a database ( table ). So, the number of primary keys in a database ( table ) defines the total number of customers in the system. Initially, If there are 5 customers, the primary key set will be { 1 , 2 , 3 , 4 , 5 }. Now if a new customer registers in the system, he will be tagged with a new primary key and the new primary key set will be { 1 , 2 , 3 , 4 , 5 , 6 }. This feature is called auto-increment as it automatically calculate the next primary key. Calculation of new primary key is done by the following rule, The first priority holder of the system is the customer with primary key 1, second priority holder of the system is the customer with primary key 2 and so on. The idea of assigning the primary key is as follows:

  if primary key exists in the database(table)
       New Primary key = Max Primary Key + 1 ;
  else 
       New Primary Key = 1 ;

If a customer deletes his/her account, all the data regarding that customer will be removed from the database. So if a customer with id number ( primary key ) 3 removes his/her account, the new primary key set will be like { 1 , 2 , 4 , 5 , 6 }. Now the third priority holder is the customer with primary key 4. So we have 4 types of queries. After parsing the “SQL-query”, the query is defined in the following manner:

  1 : A new customer is registered in the system. So insert a new primary key according to the rule.

  2 val : A registered customer removed his/her account form the system. His/her primary key is "val". Delete his/her primary key from the database. If the primary key does not exists in the database, then print "No data found".

  3 val : What is the primary key of the val'th priority holder of the system?

  4 : What is the total number of customers in the system?

Extra Example : You have a primary key set {1,2,3,4,5,6}. Then 6 is deleted. So the new list is {1,2,3,4,5}. After that, a new item is inserted. So new set will be {1,2,3,4,5,7} as for auto increment feature.

Note: You can safely assume that query of type-3, will always be valid.

Input

Input starts with a number n ( 1<=n<=109 ), denoting the current number of primary keys with set { 1 , 2 , … , n }. Each of the next lines denote a query. There will be at most 500000 queries.

Output

For query type 2 , 3 and 4, output answer based on the requirement on a line by itself.

Samples

InputOutput
5
1
4
2 3
2 3
3 3
6
No data found
4

Author
  • Kryptonyte's Avatar

    Kryptonyte

    Maruf is a student of Islamic University of Technology. In his journey of sport programming he finds inspiration from the simple things in life and aims to push beyond what he has already mastered.
Discussion
Submit

Login to submit