Алиса и Боб играют в игру. У них есть перестановка \(p\) размера \(n\) (перестановка размера \(n\) — это массив размера \(n\), где каждый элемент от \(1\) до \(n\) встречается ровно один раз). Также у них есть фишка, которую можно разместить на любом элементе перестановки.
Алиса и Боб делают ходы поочередно: Алиса делает первый ход, затем Боб делает второй ход, затем Алиса делает третий ход и так далее. Во время первого хода Алиса выбирает любой элемент перестановки и ставит фишку на этот элемент. Во время каждого из следующих ходов текущий игрок должен переместить фишку на элемент, который одновременно находится слева и строго меньше текущего элемента (т.е. если фишка находится на \(i\)-м элементе, она может быть перемещена на \(j\)-й элемент, если \(j < i\) и \(p_j < p_i\)). Если игрок не может сделать ход (переместить фишку в соответствии с правилами игры невозможно), этот игрок выигрывает в игре.
Скажем, что \(i\)-й элемент перестановки счастливый, если выполняется следующее условие:
- если Алиса поставит фишку на \(i\)-й элемент во время своего первого хода, она может выиграть игру независимо от того, как играет Боб (т.е. у нее есть выигрышная стратегия).
Ваша задача — посчитайте количество счастливых элементов в перестановке.
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество счастливых элементов в перестановке.
Примечание
В первом наборе входных данных из примера \(3\)-й элемент — счастливый.
Во втором наборе входных данных из примера нет счастливых элементов.
В третьем наборе входных данных из примера \(2\)-й элемент — счастливый.
В четвертом наборе входных данных из примера \(3\)-й и \(4\)-й элемент — счастливые.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
2 1 3
2
2 1
3
1 2 3
4
2 1 4 3
|
1
0
1
2
|