Description

The SG value of a set (multiset) is the minimum positive integer that could not be constituted of the number in this set.

You will be start with an empty set, now there are two opertions:

1. insert a number x into the set;

2. query the SG value of current set.

Input

Input contains multiple test cases. Each test case starts with a number N (0 < N <= 1e5) -- the total number of opertions.

The next N lines contain one opertion each.

1 x means insert a namber x into the set;

2 means query the SG value of current set.

Output

For each query output the SG value of current set.

Sample Input

521 121 12

Sample Output

Hint

Source

题意：

　　SG Value 是在这个集合里任意组合，不能组合成的最小的数。例：{1， 2}可以组成[1,3]的数，所以SG Value 是4。

　　有两个操作。

　　1）添加一个数进入集合

　　2）找到当前集合中的SG Value。

题解：

　　给你一个区间[L, R]，那么我们的sg value 就是 R+1。

　　一开始我们的集合是[0,0], sg value 是 1。如果我们加入2，sg value 还是1。所以我们要加入的数要小于等于 sg value 区间范围才会改变。我们就需要排个序，从小到到找。

　　而这题加入了一个添加操作，只需要用优先队列或者 multiset 来维护。

　　{1， 2， 5}，前两个来说可以组成[1,3]，就可以把他们删除掉。

优先队列　　

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #include 
          
            5 #include 
           
             6 #include 
            
              7 #include 
              8 #include 
              
                9 #include 
               
                10 #include 
                
                 11 #include 
                 
                  12 using namespace std;13 #define pb push_back14 #define mp make_pair15 #define ms(a, b) memset((a), (b), sizeof(a))16 //#define LOCAL17 #define eps 0.000000118 typedef long long LL;19 const int inf = 0x3f3f3f3f;20 const int maxn = 500+10;21 const int mod = 1000000007;22 int n;23 void solve()24 {25 priority_queue
                  
                   , greater
                   
                     >q;26 LL R = 0;27 for(int i=0;i

View Code

multiset

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #include 
          
            5 #include 
           
             6 #include 
            
              7 #include 
              8 #include 
              
                9 #include 
               
                10 #include 
                
                 11 #include 
                 
                  12 using namespace std;13 #define pb push_back14 #define mp make_pair15 #define ms(a, b) memset((a), (b), sizeof(a))16 //#define LOCAL17 #define eps 0.000000118 typedef long long LL;19 const int inf = 0x3f3f3f3f;20 const int maxn = 500+10;21 const int mod = 1000000007;22 int n;23 void solve()24 {25 multiset 
                  
                    q;26 LL R = 0;27 for(int i=0;i