Пусть \(a_1, a_2, \dots, a_n\) - отсортированная последовательность целых чисел длины \(n\) такая, что \(a_1 \leq a_2 \leq \dots \leq a_n\).
Для каждого \(1 \leq i \leq n\), префиксная сумма \(s_i\) первых \(i\) элементов \(a_1, a_2, \dots, a_i\) определяется как \(\) s_i = \sum_{k=1}^i a_k = a_1 + a_2 + \dots + a_i. \(\)
Вам заданы последние \(k\) элементов префиксных сумм, а именно \(s_{n-k+1}, \dots, s_{n-1}, s_{n}\). Ваша задача определить, возможно ли это.
Формально, дано \(k\) целых чисел \(s_{n-k+1}, \dots, s_{n-1}, s_{n}\), задача состоит в том, чтобы проверить, есть ли последовательность целых чисел \(a_1, a_2, \dots, a_n\) такая, что
- \(a_1 \leq a_2 \leq \dots \leq a_n\), и
- \(s_i = a_1 + a_2 + \dots + a_i\) для всех \(n-k+1 \leq i \leq n\).
Выходные данные
Для каждого набора входных данных выведите «YES» (без кавычек) если это возможно и «NO» (без кавычек) в противном случае.
Вы можете выводить «YES» и «NO» в любом регистре (например, строки «yEs», «yes» и «Yes» будут распознаны как положительный ответ).
Примечание
В первом наборе входных данных подходит только \(a = [1, 1, 1, 1, 1]\).
Во втором наборе входных данных мы можем выбрать \(a = [-3, -2, -1, 0, 1, 2, 3]\).
В третьем наборе входных данных подходит только \(a = [2, 1, 1]\), но это не отсортированная последовательность.
В четвертом наборе входных данных может быть показано, что такой последовательности не существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5 5
1 2 3 4 5
7 4
-6 -5 -3 0
3 3
2 3 4
3 2
3 4
|
Yes
Yes
No
No
|