eolymp
Задачі

Вибори вождя

Вибори вождя

Орки – одна з рас, що населяють світ Драенор. Не відрізняючись високим інтелектом, орки все ж таки славляться своєю силою та відвагою у бою. Щорічно орки з різних кланів збираються в Долині Сили для того, щоб вибрати вождя всієї Орди. На відміну від нерозумних людей, орки зневажають вибори шляхом голосування (да і, скажемо відверто, всі ці бюлетені, урни та виборчі дільниці - чужі і незрозумілі орку, який не тримав в руках нічого, крім палиці та сокири). Кандидати у вожді змагаються один з одним в чесних поєдинках. У кожному поєдинку приймають участь два претенденти, один з яких виходить з нього переможцем, а інший стає переможеним. Орк, що програв у одному з поєдинків, вибуває з числа претендентів і не может приймати участь в наступних поєдинках. Той, хто залишився останнім після всіх боїв кандидат і стає вождем Орди.

Старійшини орків завжди спостерігають за виборами і люблять передбачати, хто в них переможе. Проте далеко не завжди можна передбачити не те, что загальну перемогу на виборах, а навіть переможця в одному конкретному бою. Звичайно ж все залежить від сили суперників – хто сильніший, той і переможе, проте у випадку рівності сил може перемогти будь-хто з них – тут вже як зірки ляжуть.

Старійшини звернулись до вас з проханням написати програму для визначення кількості претендентів, які можуть стати вождями.

prb176

Вхідні дані

У першому рядку вхідного файлу задано кількість N претендентів на звання вождя в цьому році (1N1000000), у другому – N цілих чисел в межах від 1 до 10000, кожне з яких визначає силу відповідного кандидата.

Вихідні дані

Вихідний файл повинен містити одне число – кількість претендентів, які можуть стати вождями.

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
5
1 2 3 4 5
Вихідні дані #1
1
Автор vetal_n