Знаменитый писатель Велепин очень продуктивный. Совсем недавно он подписал контракт с известным изданием и теперь ему нужно написать \(k_i\) книг за \(i\)-й год. Для него это вообще не проблема, он может сколько угодно писать о самураях, космосе, пустоте, насекомых и оборотнях.
У него есть \(n\) постоянных читателей, каждый из которых в \(i\)-й год прочитает одну из \(k_i\) книг, выпущенных Велепиным. Читатели очень любят обсуждать книги, поэтому \(j\)-й из них будет доволен в течение года, если такую же книгу, как он, прочитают как минимум \(a_j\) человек (включая его самого).
У Велепина есть явные проблемы с маркетингом, поэтому он обратился к вам! Известный сервис чтения книг может управлять тем, что будет читать каждый из поклонников Велепина, но он не хочет чтобы книги пропадали зря, поэтому каждую книгу должен кто-то прочитать. И вот они обратились к вам, с просьбой сказать, какое максимальное количество постоянных читателей можно сделать довольным в течение каждого из годов, если вы можете выбирать каждому человеку книгу, которую он будет читать.
Выходные данные
Выведите \(q\) строк, в каждой из них ровно одно число — максимальное количество человек, которые могут быть довольны в \(j\)-й год, если Велепин выпустит \(k_j\) книг.
Примечание
В первом примере в первый год оптимальным является разделение \(1, 2, 2, 2, 2\) (первую книгу читает первый человек, а все остальные вторую). Во второй год оптимальным решением является \(1, 2, 2, 3, 3\) (первую книгу читает первый человек, вторую книгу читает второй и третий человек, а все остальные третью книгу). В третий год оптимальным будет разбиение \(1, 2, 3, 4, 2\). Соответственно количество довольных людей по годам будет — \(5, 5, 3\).
Во втором примере в первый год оптимальным является разделение \(1, 1, 1, 1, 1, 2\), тогда будут довольны все кроме \(6\)-го человека. Во второй год оптимальным разделением является \(1, 1, 1, 1, 2, 3\), тогда будут довольны все кроме \(5\)-го и \(6\)-го человека.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2 2 2 2
3
2
3
4
|
5
5
3
|
|
2
|
6
1 2 3 4 5 6
2
2
3
|
5
4
|
|
3
|
6
4 4 1 4 4 4
3
2
3
4
|
6
5
1
|