Вам дан массив целых положительных чисел \(a_1, a_2, \ldots, a_n\).
Найдите количество пар индексов \((l, r)\) (\(1 \le l \le r \le n\)), которые проходят проверку. Проверка пары чисел выполняется следующим образом:
- Находятся минимум и максимум среди чисел \(a_l, a_{l+1}, \ldots, a_r\).
- Проверка считается пройденной, если максимум делится на минимум.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — количество проходящих проверку пар чисел.
Примечание
Ниже запись \(x \mid y\) означает, что \(y\) делится на \(x\).
В первом наборе входных данных существует всего одна пара индексов \((1, 1)\), для нее максимум равен \(1\), минимум также \(1\), \(1 \mid 1\), поэтому эта пара проходит проверку, а ответ равен \(1\).
Во втором наборе входных данных \(3\) пары индексов:
- \((1, 1)\): максимум равен \(2\), минимум равен \(2\), \(2 \mid 2\), проверка пройдена.
- \((1, 2)\): максимум равен \(4\), минимум равен \(2\), \(2 \mid 4\), проверка пройдена.
- \((2, 2)\): максимум равен \(4\), минимум равен \(4\), \(4 \mid 4\), проверка пройдена.
В третьем наборе входных данных \(3\) пары индексов:
- \((1, 1)\): максимум равен \(2\), минимум равен \(2\), \(2 \mid 2\), проверка пройдена.
- \((1, 2)\): максимум равен \(3\), минимум равен \(2\), \(3\) не делится на \(2\), поэтому проверка не пройдена.
- \((2, 2)\): максимум равен \(3\), минимум равен \(3\), \(3 \mid 3\), поэтому проверка пройдена.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1
1
2
2 4
2
2 3
4
2 4 7 14
7
16 5 18 7 7 12 14
6
16 14 2 6 16 2
|
1
3
2
7
10
19
|