eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Сбалансированное фото

Сбалансированное фото

Фермер Джон выстроил свои n коров в ряд, чтобы сделать фото. Высота i-ой коровы в этой последовательности равна hi, и все эти высоты различны.

ФД хочет, чтобы фотография получилась красивее. Он считает, что корова i выглядит несбалансированно, если Li и Ri отличаются более чем в 2 раза. Здесь Li и Ri - количества коров, которые выше чем корова i, слева и справа соответственно. То есть, корова i является несбалансированной, если большее из чисел Li и Ri строго более чем в 2 раза больше, чем меньшее из этих двух чисел.

Вычислите сколько всего есть несбалансированных коров.

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

Первая строка содержит число n (1n105). Следующие n строк содержат h1 .. hn, каждое неотрицательное целое не более чем 109.

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

Выведите количество несбалансированных коров.

Пояснение

В этом примере коровы с высотами 34, 5, 3 несбалансированны.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
7
34
6
23
0
5
99
2
Вихідні дані #1
3
Джерело 2017 USACO Январь, Золото