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

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

加入题单

上一题 下一题 算法标签: