Фермер Джон выстроил свои n коров в ряд, чтобы сделать фото. Высота i-ой коровы в этой последовательности равна h[i]
, и все эти высоты различны.
ФД хочет, чтобы фотография получилась красивее. Он считает, что корова i выглядит несбалансированно, если L[i]
и R[i]
отличаются более чем в 2 раза. Здесь L[i]
и R[i]
- количества коров, которые выше чем корова i, слева и справа соответственно. То есть, корова i является несбалансированной, если большее из чисел L[i]
и R[i]
строго более чем в 2 раза больше, чем меньшее из этих двух чисел.
Вычислите сколько всего есть несбалансированных коров.
Первая строка содержит число n (1 ≤ n ≤ 10^5
). Следующие n строк содержат h[1]
.. h[n]
, каждое неотрицательное целое не более чем 10^9
.
Выведите количество несбалансированных коров.
В этом примере коровы с высотами 34, 5, 3 несбалансированны.