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.|

FR_07_20 - Lider II

W Dwójkolandii przyszedł czas na długo wyczekiwane wybory. Okręgi wyborcze wystawiły swoich kandydatów, a wyborcy zapoznali się z ich planami wyborczymi. Dziś jest dzień wyborów, a ty zostałeś powołany na wolontariat polegający na zliczaniu głosów i określeniu, czy w danym okręgu wyborczym jakiś kandydat osiągnął więcej niż 50% głosów. System wyborczy w Dwójkolandii działa następująco. Wyborcy należący do danego okręgu wyborczego są zapisani na spójnej liście, jeden za drugim, itd. Wszystkie listy połączone są w jedną wielką listę. Dodatkowo każdy wyborca ma prawo zmienić swój wybór i zaznaczyć innego kandydata - taki system :). Ty jednak jesteś bardzo sprytną osobą i pojąłeś trudną sztukę programowania. Napisz program, który znacznie ułatwi ci pracę na wolontariacie, wyznaczający lidera w przedziale liczb. Wykonujemy dwie operacje. Pierwsza, to zmiana wyboru kandydata na inny (zmiana decyzji wyborcy), druga to sprawdzenie, czy w okręgu zaczynającym się od wyborcy na pozycji a a kończącym się na wyborcy na pozycji b został wybrany kandydat do rządzenia Dwójkolandią - tzn. liczba oddanych głosów na tę osobę jest większa niż 50%.

Wejście

W pierwszym wierszu jedna liczba n określająca liczbę wyborców (nie więcej niż 106).

W drugim wierszu n liczb naturalnych określających głosy wyborców. Każdy kandydat jest reprezentowany przez liczbę mieszczącą się w przedziale [0..109]. Jeden kandydat może być wybierany w kilku okręgach (taki system :)).

W trzecim wierszu jedna liczba q określająca liczbę zapytań (nie więcej niż 106).

Specyfikacja każdego zapytania:

najpierw jeden znak i lub q, następnie dwie liczby całkowite. Jeśli pojawi się i, zostaną podane dwie liczby całkowite x i y, oznaczające, że należy podmienić decyzję wyborcy z pozycji x w ciągu na y, natomiast, gdy pojawi się znak q, to pojawią się dwie liczby a i b, definiujące przedział [a...b], w którym należy określić, czy występuje lider w tym przedziale (1 ≤ x n, 0 ≤ y ≤ 109, 1 ≤ a b n).

Wyjście

Dla każdego zapytania, w którym wystąpiła litera q należy wypisać lidera zbioru w przedziale [a..b], lub napis brak, gdy lider nie występuje.

Przykład

Wejście:
6
2 2 3 2 7 8
5
q 1 4
q 1 1
i 3 7
q 3 5
q 3 6


Wyjście:
2
2
7
brak

Dodane przez:Marcin Kasprowicz
Data dodania:2017-04-07
Limit czasu wykonania programu:1s-5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.