Задача C. Султан и мудрецы

Автор:Н. Малявин, М. Спорышев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Однажды султан решил проверить знание математики у своих мудрецов.

Для этого он собрал N мудрецов, и потребовал от них назвать N различных натуральных чисел, дающих в сумме указанное число D.

Мудрецы начал выступать по очереди, i-й мудрец называл число ai. И вот очередь дошла до N − 1-го мудреца — Васи.

От числа, которое назовет Вася, зависит судьба всех мудрецов. Помогите мудрецу Васе найти такое ещё не названное число aN − 1, чтобы последний мудрец имел возможность назвать число aN, отличающееся от всех предыдущих чисел и дополняющее их сумму до D.

Рекомендуется рассмотреть следующие частичные решения

Формат входного файла

Входной файл содержит натуральные числа D N, за которыми следует N − 2 натуральных числа ai — числа, названные мудрецами до Васи.

Формат выходного файла

Выходной файл должен содержать подходящее для Васи число, либо  − 1, если такого числа не существует.

Если решений несколько, выведите любое из них.

Ограничения

3 ≤ N ≤ 105

1 ≤ D, ai ≤ 109, ai ≠ aj∀ i ≠ j

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
18 4
2 6
1
2
26 5
2 5 9
4
3
13 4
2 5
-1

0.077s 0.009s 13