Фермер Джон выстроил свои \(N\) коров в ряд, чтобы сделать фото.
(\(1 \leq N \leq 100,000\)). Высота \(i\)-ой коровы в этой последовательности
равна \(h_i\), и все эти высоты различны.
ФД хочет, чтобы фотография получилась красивее. Он считает, что корова \(i\)
выглядит несбалансированно, если \(L_i\) и \(R_i\) отличаются более чем в 2 раза.
Здесь \(L_i\) и \(R_i\) - количества коров, которые выше чем корова \(i\), слева и
справа соответственно. То есть, корова \(i\) является несбалансированной, если
большее из чисел \(L_i\) и \(R_i\) строго более чем в 2 раза больше, чем меньшее
из этих двух чисел.
Вычислите сколько всего есть несбалансированных коров.
ФОРМАТ ВВОДА (файл bphoto.in):
Первая строка ввода содержит число \(N\). Следующие \(N\) строк содержат
\(h_1 \ldots h_N\), каждое неотрицательное целое не более чем 1,000,000,000.
ФОРМАТ ВЫВОДА (файл bphoto.out):
Выведите количество несбалансированных коров.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
34
6
23
0
5
99
2
|
3
|