Дима Ватрушин работает учителем алгебры в школе. За хорошую работу его отправили в отпуск на \(n\) дней. Дима давно мечтал съездить на горнолыжный курорт, поэтому он хочет выделить несколько дней подряд и отправиться кататься на лыжах. Так как поездка требует тщательной подготовки, то он готов поехать минимум на \(k\) дней.
Вам дан массив \(a\), содержащий прогноз погоды на курорте. То есть в \(i\)-й день температура будет равна \(a_i\) градусов.
Дима родился в Сибири, поэтому он сможет отправиться отдохнуть, только если температура не поднимется выше \(q\) градусов на протяжении всей поездки.
К сожалению, Дима настолько увлекся абстрактной алгеброй, что разучился считать. Он просит вас помочь ему и посчитать количество способов выбрать даты отдыха на курорте.
Выходные данные
Выведите \(t\) чисел, каждое из которых является ответом на соответствующий набор — количество способов Диме выбрать даты отдыха на курорте.
Примечание
В первом наборе входных данных примера Дима может поехать в любой день, поэтому ему подходят даты [1], [2], [3], [1, 2], [2, 3], [1, 2, 3].
Во втором и четвертом наборах входных данных примера Дима не может поехать ни в какой день из-за высокой температуры, поэтому подходящих дат нет.
В третьем наборе входных данных примера Дима может поехать только в даты [1, 2, 3].
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
3 1 15
-5 0 -10
5 3 -33
8 12 9 0 5
4 3 12
12 12 10 15
4 1 -5
0 -1 2 5
5 5 0
3 -1 4 -5 -3
1 1 5
5
6 1 3
0 3 -2 5 -4 -4
|
6
0
1
0
0
1
9
|