Algorithmen Übungen WS13/14

Beim Aktienhandel gibt es einerseits diejenigen, die eine Aktie verkaufen wollen, und diejenigen, die eine Aktie kaufen wollen. Jeder Verkäufer gibt an, zu welchem Preis er bereit ist, seine Aktie zu verkaufen, und der Käufer gibt an, zu welchem Preis er bereit ist, eine Aktie zu kaufen. Gibt es dann mal einen Käufer, der mindestens soviel zahlen will wie ein Verkäufer fordert, kommt es zu einem Handel. Dabei handelt immer derjenige mit dem derzeit niedrigsten Verkaufsangebot mit demjenigen mit dem derzeit höchsten Kaufangebot.

Sie bekommen eine Liste von zeitlich aufeinanderfolgenden Kauf- und Verkaufangeboten. Ihre Aufgabe ist es nun zu bestimmen, wann genau es jeweils zu einem Handel kommt.

Eingabe

Die Eingabe beginnt mit einer Zahl n (1 ≤ n ≤ 500000). Die folgende Zeile enthält n Zahlen im Bereich von -1000000 und 1000000. Eine negative Zahl a_i bedeutet ein Verkaufsangebot zum Preis von -a_i, eine positive Zahl a_i bedeutet ein Kaufangebot zum Preis von a_i. Die Zahl 0 kommt nicht in der Eingabe vor.

Ausgabe

Immer, wenn nach Eingabe einer Zahl a_i ein Handel zustandekommt, geben Sie eine Zeile aus mit: „Handel in Schritt i” (ohne Anführungszeichen).

Beispiel

Eingabe:
8
2 -4 3 -6 5 4 -4 -4

Ausgabe:
Handel in Schritt 5
Handel in Schritt 7