410416: GYM104018 I 42 причины посетить Вьетнам

I. 42 причины посетить Вьетнамограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

В поисках ответа на главный вопрос жизни, вселенной и всего такого Айбек отправился в Ханой.

Почему в Ханой? Потому что за свою жизнь много раз слышал о «Ханойских башнях» — раз все об этом говорят, то надо обязательно изучить вживую.

И Айбеку улыбнулась удача. Первая же башня (а точнее её древние развалины), которые он нашёл, состояла из каменных круглых дисков, насаженных центром на один большой столб.

Что еще более заинтересовало Айбека — каждый следующий в направлении к небу диск имел радиус не больше, чем у предыдущего.

«Наверное, так богам на небесах было видно больше различных дисков», — подумал Айбек.

Чтобы проверить свою гипотезу, Айбек просит вас (как самого опытного экскурсовода по Вьетнаму) вычислить количество дисков, которые видно, если смотреть на центральную ось башни строго сверху с очень-очень большой высоты.

Диск видно, если его радиус строго больше всех радиусов дисков, расположенных ближе к небу.

Входные данные

В первой строке расположено одно целое число $$$N$$$ $$$(1 \le N \le 3 \cdot 10^5)$$$ — количество дисков Ханойской башни.

Во второй строке через пробел задано $$$N$$$ целых чисел $$$r_i$$$ $$$(1 \le r_n \le r_{n-1} \le \dots \le r_2 \le r_1 \le 10^6)$$$ — радиусы дисков в направлении от земли к небу.

Выходные данные

Выведите единственное целое число — количество дисков, которые видно, если смотреть на центральную ось башни строго сверху с очень-очень большой высоты.

ПримерыВходные данные

3
42 13 8

Выходные данные

3

Входные данные

7
9 9 4 2 2 2 1

Выходные данные

4

Примечание

Первый тестовый пример

У всех дисков башни радиус различен, поэтому каждый диск будет видно с «высоты богов».

Второй тестовый пример

Боги точно увидят диски под номерами $$$2$$$, $$$3$$$, $$$6$$$ и $$$7$$$:

• Диск $$$1$$$ не видно, так как он полностью скрыт диском $$$2$$$;
• Диски $$$4$$$ и $$$5$$$ полностью скрыты диском $$$6$$$.