Монокарп играет в шахматы на одном популярном сайте. На этом сайте у него есть \(n\) соперников. Рейтинг \(i\)-го соперника равен \(a_i\). Изначальный рейтинг Монокарпа равен \(x\). Монокарп хочет достичь рейтинга \(y\) (\(y > x\)).
Когда Монокарп играет партию, он побеждает, если его текущий рейтинг больше или равен рейтинга противника. В случае победы рейтинг Монокарпа повышается на \(1\), в случае поражения — понижается на \(1\). Рейтинг его противника не меняется.
Монокарп хочет за минимальное кол-во партий достигнуть рейтинга \(y\). Но сайт не позволяет ему легко набирать рейтинг в играх против слабых игроков, требуя, чтобы Монокарп играл со всеми противниками примерно равное количество партий. Формально, Монокарп может сыграть партию с противником \(i\) только если нет другого противника \(j\) такого, что Монокарп сыграл против \(i\) больше раз, чем против \(j\).
Посчитайте минимальное кол-во партий, которое нужно сыграть Монокарпу, чтобы достичь рейтинга \(y\), или скажите, что это невозможно. Заметьте, что рейтинги противников Монокарпа остаются неизменными, в отличие от рейтинга самого Монокарпа.
Выходные данные
Для каждого набора входных данных выведите одно число — минимальное количество партий, которые нужно сыграть Монокарпу, чтобы получить рейтинг \(y\), или \(-1\), если достичь данного рейтинга невозможно.
Примечание
В первом наборе входных данных, Монокарп может использовать следующую стратегию:
- Монокарп играет против \(2\)-го соперника и увеличивает рейтинг (\(2 \to 3\));
- Монокарп играет против \(1\)-го соперника и увеличивает рейтинг (\(3 \to 4\));
- Монокарп играет против \(4\)-го соперника и увеличивает рейтинг (\(4 \to 5\));
- Монокарп играет против \(5\)-го соперника и увеличивает рейтинг (\(5 \to 6\));
- Теперь Монокарп должен сыграть с оставшимися тремя соперниками. Он проиграет \(3\) раза и получит рейтинг \(3\) (\(6 \to 5 \to 4 \to 3\));
- После этого Монокарп повторит шаги 1-5 два раза. После \(14\) партий получится, что он сыграл дважды к каждым противников и его финальный рейтинг равен \(4\).
- Монокарп играет против \(1\)-го соперника и увеличивает рейтинг (\(4 \to 5\));
- Монокарп играет против \(2\)-го соперника и увеличивает рейтинг (\(5 \to 6\));
- Монокарп играет против \(4\)-го соперника и увеличивает рейтинг (\(6 \to 7\));
- Монокарп играет против \(5\)-го соперника и увеличивает рейтинг (\(7 \to 8\));
- Монокарп играет против \(7\)-го соперника и увеличивает рейтинг (\(8 \to 9\));
- Монокарп играет против \(3\)-го соперника и увеличивает рейтинг (\(9 \to 10\));
В результате Монокарп сыграл дважды с
\(6\)-м противником и трижды со всеми остальными, получив рейтинг
\(10\) за
\(14 + 6 = 20\) партий.
Во втором наборе можно показать, что какие бы партии не сыграл Монокарп, он не сможет получить рейтинг выше \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
7 2 10
3 1 9 2 5 20 8
7 1 10
3 1 9 2 5 20 8
5 10 12
100 1 200 11 300
|
20
-1
2
|