Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

TICKETS - Ticket Verlosung

Byteland organisiert die Fußball WM. Ein Radiosender hat einige der Eintrittskarten erworben und bietet eine Verlosung an. Genauer gesagt handelt es sich hierbei um ein Telefonspiel, bei dem jeder Teilnehmer eine Zahl zwischen 1 und 109 wählen kann, and am Ende jeden Tages bekommt derjenige eine Eintrittskarte, der die k.-kleinste Zahl gewählt hat. Um zu verhindern, dass es mehr als einen Gewinner gibt, darf jede Zahl nur einmal gewählt werden. Falls also ein Teilnehmer eine Zahl wählt, die schon vergeben ist, muss er einfach noch einmal wählen.

Martin, ein fanatischer Fußballfan ohne Eintrittskarten, hat Robert H., einen Angestellten des Radiosenders, bestochen und ihm Geschenke versprochen für den Fall, dass er ihm eine derzeitige Gewinnzahl nennt: "Einen Korb mit Spezialitäten aus dem Schwarzwald, der einige richtig gute Würstchen enthält, Schinken, und - halten Sie sich fest - eine wunderschöne Kuckucksuhr! Und dazu noch einen Bierkrug! Wie können Sie da widerstehen?"

Natürlich konnte Robert diesem verlockenden Angebot nicht widerstehen und braucht nun ein Programm, das ihm zu beliebigen Zeiten während dem Spiel die k.-kleinste Zahl berechnet.

 

Eingabe

Die erste Zeile in der Eingabe enthält eine Zahl c (1 ≤ c ≤ 106), die angibt, wieviele Telefonanrufe der Sender bekommt. Die folgende Zeile der Eingabe enthält die Zahl k (1 ≤ k ≤ min(c, 100000) ). Die folgenden c Zeilen geben die gewählten Zahlen der Teilnehmer des Gewinnspiels an in der zeitlichen Reihenfolge ihrer Anrufe bei dem Radiosender. Alle diese Zahlen liegen zwischen 0 und 109, wobei eine Zahl 0 bedeutet, dass Martin Robert angerufen hat und wissen will, was die derzeit k.-kleinste Zahl ist. Die Zahl 0 wird hierbei nicht in die Liste möglicher Gewinnzahlen aufgenommen. Für alle Zahlen > 0 gilt, dass sie nur einmal in der Eingabe vorkommen.

Ausgabe

Geben Sie für jede Zahl 0 in der Eingabe, die einem Anruf von Martin entspricht, eine Zeile aus mit der k.-kleinsten Zahl zu diesem Zeitpunkt. Falls bis dahin noch keine k Zahlen gewählt wurden, geben Sie -1 aus.

Beispiel

Eingabe:
7
2
4711
0
1337
0
210706
3
0
Ausgabe:
-1
4711
1337

Achtung! Die Anzahl der Abfragen nach der k.-kleinsten Zahl kann sehr groß sein (z. B. jeder zweite Anruf). Eine effiziente Datenstruktur wird benötigt.


Added by:Adrian Kuegel
Date:2008-10-27
Time limit:10s-32s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.