Sublime Text Мальчик Дима написал решение для задачи с отбора на Высшую Пробу. Его код представляет собой n строк, где строка i содержит si позиций для курсора. Обозначим j-ю позицию в i-й строке как (i, j).

Решение все никак не заходит, поэтому Дима решил воспользоваться своей новой техникой дебага кода.

В его редакторе есть две кнопки, которые работают по естественным правилам:

Up: если курсор находится в положении (i, j), то при i = 1 курсор остается на месте, иначе сдвигается в положение (i - 1, min(j, si - 1)).

Right: если курсор находится в положении (i, j), то при j < si курсор передвигается в (i, j + 1), иначе в (i + 1, 1), кроме случая (n, sn) - тогда он остается на месте.

Для дебага Дима выбирает себе некоторое положение курсора и последовательно повторяет следующую операцию, состоящую из комбинации нажатий: u раз Up, затем r раз Right.

Например при n = 5, u = 2, r = 5, s = {5, 2, 4, 3, 1}, стартовом положении (4, 3), будет следующая последовательность позиций:

(4, 3) Up (3, 3) Up (2, 2) Right (3, 1) Right (3, 2) Right (3, 3) Right (3, 4) Right (4, 1)

Положение называется успешным, если в какой-то момент (возможно внутри операции), курсор окажется в первой строке.

Диме посчитать, сколько успешных положений в его коде.

Формат входных данных
Первая строка теста содержит одно целое число t (t ≤ 10) - количество наборов тестовых данных. Затем следуют t наборов тестовых данных.

Первая строка набора тестовых данных содержит три целых числа n, u, r (1 ≤ n ≤ 105, 1 ≤ u, r ≤ 1018).

Вторая строка набора тестовых данных содержит n целых чисел s1, s2, ..., sn (1 ≤ si ≤ 1012).

Формат результата
Для каждого набора тестовых данных выведите одно целое число - ответ на него

Примеры
Входные данные
2
5 2 5
5 2 4 3 1
5 2 10
5 2 4 3 1
Результат работы
15
11
Входные данные
1
10 1 42
169 42 42 42 42 42 42 42 42 42
Результат работы
211
Примечания
Система оценки:

sums = s1 + s2 + ... + sn
Группа Дополнительные ограничения Комментарий
n sums u, r
0 0 - - - Тесты из условия
1 8 n ≤ 100 sums ≤ 100 u, r ≤ 100 -
2 10 - sums ≤ 105 - -
3 2 - - u = 1, r = 1 -
4 10 - - - -
Если ваше решение работает корректно на всех тестах некоторой подгруппы, то оно наберет за нее не меньше указанного количества . Тесты по подгруппам не пересекаются. Подгруппы складываются

Путь из (5, 1) в первом тестовом случае первого теста:

Шаг 1: (5, 1) Up (4, 1) Up (3, 1) Right (3, 2) Right (3, 3) Right (3, 4) Right (4, 1) Right (4, 2)

Шаг 2: (4, 2) Up (3, 2) Up (2, 2) Right (3, 1) Right (3, 2) Right (3, 3) Right (3, 4) Right (4, 1)

Шаг 3: (4, 1) Up (3, 1) Up (2, 1) Right (2, 2) Right (3, 1) Right (3, 2) Right (3, 3) Right (3, 4)

Шаг 4: (3, 4) Up (2, 2) Up (1, 2) Right ...

Bomberidze    1   23.11.2020 14:04    1