У вас есть несколько карточек, на каждой из которых написано целое число от \(1\) до \(n\). В частности, для каждого \(i\) от \(1\) до \(n\) у вас есть \(a_i\) карточек, на которых написано число \(i\).
Также есть магазин, который содержит неограниченное количество карточек каждого типа. У вас есть \(k\) монет, поэтому вы можете купить в общей сложности \(k\) дополнительных карточек, а купленные вами карточки могут содержать любые целые числа от \(1\) до \(n\).
После покупки новых карточек вы расставляете все свои карточки в линию. Счет расстановки — это количество (непрерывных) подмассивов длины \(n\), которые являются перестановкой массива \([1, 2, \ldots, n]\). Какой максимальный счет вы можете получить?
Примечание
В первом наборе входных данных искомый (и единственный) массив, который можно получить, — это \([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\) (\(11\) карточек с числом \(1\)), который содержит \(11\) подмассивов, состоящих из перестановки \([1]\).
Во втором наборе входных данных мы можем купить \(0\) карточек типа \(1\) и \(4\) карточки типа \(2\), а затем расставить карточки следующим образом: \([1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]\). Есть \(8\) подмассивов, равных \([1, 2]\), и \(7\) подмассивов, равных \([2, 1]\), что в сумме составляет \(15\) подмассивов, которые являются перестановкой \([1, 2]\). Можно также доказать, что это максимальный счет, который мы можем получить.
В третьем наборе входных данных одной из возможных оптимальных расстановок является \([3, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 3]\).