Giải bài trực tuyến

Farmer John (FJ) vừa mua đuợc một cái cỗ máy thời gian. FJ có thể tiến tới một thời gian nào đó trong tuơng lai bằng cách cứ cho thời gian trôi (không thể sử dụng máy thời gian vì tuơng lai chưa định sẵn/bị đảo lộn) hoặc quay trở lại mốc thời gian nào đó trong quá khứ.

            FJ  muốn đạt đuợc sản luợng nhiều nhất có thể . Vì thế anh ấy đã thống kê , ghi lại sản lụơng những con bò cung cấp trong quá trình nuôi hoặc sau khi có một truy vấn hành động nào đó làm tác động đến đàn bò. FJ chỉ quan tâm đến chỉ số ID của con bò mà anh ấy nuôi trong thời gian ngắn nhất . Hãy viết chuơng trình xác định và in ra các số ID ấy sau mỗi truy vấn hành động (hoặc in ra -1 nếu FJ chẳng còn con bò nào !)

            FJ có tập gồm N (1 ≤ N ≤ 80,000) sự kiện đuợc đánh số từ 1..N thể hiện sự thay đổi trong đàn bò theo thời gian biểu của FJ. Mỗi truy vấn đuợc ghi trên một dòng gồm có một kí tự c và một số nguyên K  (1 ≤ K ≤ 100,000) nếu như c = ‘a’ hoặc c = ‘t’ . Các sự kiện có sau

-          Nếu c = ‘a’ thì John thêm một con bò có số ID là K vào đàn bò.

-          Nếu c = ‘s’ thì John bán đi con bò có số ngày nuôi ít nhất.

-          Nếu c = ‘t’ thì John dùng cỗ máy thời gian trở lại thời điểm truớc khi thực hiện truy vấn K và đàn bò sẽ trở lại như lúc thời điểm truớc K .

Input

- Dòng đầu tiên ghi số nguyên N

- N dòng tiếp theo ghi các truy vấn

 Output

- Gồm N dòng . Mỗi dòng ghi số ID của con bò có ngày nuôi ngắn nhất 

------------------------------------------------------------------------

Ta có ví dụ sau . Với N = 12 và các truy vấn , ta có output sau

    #   T.vấn   Đàn bò      Kết quả     Giải thích

     1   a 5  -> [5]        => 5        Thêm một con bò có ID = 5

     2   a 3  -> [5,3]      => 3        Thêm một con bò có ID = 3

     3   a 7  -> [5,3,7]    => 7        Thêm một con bò có ID = 7

     4   s    -> [5,3]      => 3        Bán con bò có ID = 7

     5   t 2  -> [5]        => 5        Quay ngụơc thời gian truớc #2

     6   a 2  -> [5,2]      => 2        Thêm một con bò có ID = 2

     7   t 4  -> [5,3,7]    => 7        Quay ngụơc thời gian truớc #4

     8   a 4  -> [5,3,7,4]  => 4        Thêm một con bò có ID = 4

     9   s    -> [5,3,7]    => 7        Bán con bò có ID = 4

    10   t 7  -> [5,2]      => 2        Quay ngụơc thời gian truớc #7

    11   s    -> [5]        => 5        Bán con bò có ID = 2

    12   s    -> []         => -1       Bán con bò có ID = 5

12

a 5

a 3

a 7

s

t 2

a 2

t 4

a 4

s

t 7

s

s

5

3

7

3

5

2

7

4

7

2

5

-1