TTRAVEL - Time Travel

• Thời gian: 0.2s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

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

Ví dụ

Input
12
a 5
a 3
a 7
s
t 2
a 2
t 4
a 4
s
t 7
s
s

Output
5
3
7
3
5
2
7
4
7
2
5
-1

• Người up: hlong290494
• Nguồn bài: USACO US Open 2010