FRAKTAL - konkurs programistyczny

Zasady gry. Wyobraźmy sobie oś liczbową na której umieszczamy bańki poruszające się w lewo lub w prawo. Wszystkie bańki poruszają się ze stałą prędkością niektóre w lewo inne w prawo. Jeśli dojdzie do kolizji, tzn. spotkają się dwie bańki, które poruszają się w przeciwnych kierunkach, to następuje jedna z dwóch sytuacji:

• jeśli bańki są różnej wielkości, to większa pochłania mniejszą zwiększając swoją objętość o tą zjedzoną
• jeśli bańki są równej wielkości, to bańki pękają, gdyż żadna z nich nie jest w stanie pochłonąć bańki równej sobie.

Twoim zadaniem jest określenie początkowych pozycji baniek, które ukończą grę. Bańka ukończy grę, wtedy i tylko wtedy, gdy uda jej się opuścić oś.

Wejście

W pierwszym wierszu jedna liczba n określająca liczbę baniek na osi (nie więcej niż milion)

W drugim wierszu n baniek w postaci liczby całkowitej reprezentującej objętość bańki (objętości baniek mieszczą się w przedziale [1..10⁶].

W trzecim wierszu n znaków należących do zbioru {l, r} określających kierunek poruszania się baniek. I-ty znak określa kierunek i-tej bańki: l - w lewo, r - w prawo.

Wyjście

Początkowe pozycje baniek, które opuszczą planszę gry. Pozycje podajemy jako rosnący ciąg. Pierwsza bańka wysunięta najbardziej na lewo ma numer 1, druga 2 itd.

Przykład

Wejście:
5
2 4 3 2 1
r r l r l

wyjście:
1 2 4