Есть группа из \(n\) человек. Некоторые из них могут быть лжецами, которые всегда лгут. Остальные люди всегда говорят правду. \(i\)-й человек сказал: «Среди нас не менее \(l_i\) лжецов». Определите, является ли сказанное людьми противоречивым, или это возможно. Если это возможно, выведите количество лжецов в группе. Если ответов несколько, вы можете вывести любой из них.
Выходные данные
Для каждого набора входных данных выведите одно целое число. Если сказанное людьми противоречиво, выведите \(-1\). Иначе выведите количество лжецов в группе. Если ответов несколько, вы можете вывести любой из них.
Примечание
В первом примере единственный возможной ответ, это что лжет второй человек, откуда ответ \(1\) лжец.
Во втором примере можно показать, что невозможно выбрать лжецов, так чтобы все высказывания удовлетворяли условию.
В третьем примере все говорят правду, откуда ответ \(0\) лжецов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
2
1 2
2
2 2
2
0 0
1
1
1
0
5
5 5 3 3 5
6
5 3 6 6 3 5
|
1
-1
0
-1
0
3
4
|