Кооперація (Coop) (юніори+ старша ліга)
Гноми-велетні знамениті своїми гігантськими розмірами та любов'ю до золота. В одному з поселень гномів існує N пар гномів, причому в i-ій (1 ≤ i ≤ N) парі як чоловік-гном, так і жінка-гном мають зріст рівно i. Крім того, кремезні чоловіки-гноми зазвичай виступають у якості опори, у той час як тендітні жінки-гноми вправно орудують киркою. Геологічна розвідка виявила неподалік селища гномів вертикальну нескінченно високу скелю. Гноми вирішили, що там з великою вірогідністю буде золото, тож домовилися вранці вирушити на полювання на нього. Щоправда, дійшовши до скелі, гноми виявили проблему: K сімей не прийшли на зустріч. Гноми збираються довбати скелю в наступний спосіб: нехай якийсь чоловік-гном зросту A виступає опорою для якоїсь жінки-гнома зросту B. Разом цей тандем здатний довбати скелю лише на висоті A + B. Для кожної висоти обирається підходящий тандем, причому будь-який присутній гном може виступати (в різні моменти часу) у складі різних тандемів. Тепер гномів цікавить, скільки ж існує досяжних висот. Іншими словами, для скількох висот знайдеться підходящий тандем?
Формат введення-виведення: Програма Coop спочатку зчитує з клавіатури (стандартного пристрою введення) два цілих числа N(1 ≤ N ≤ 2·109) та K (1 ≤ K ≤ min{N, 10000}) – кількість пар гномів у поселенні та кількість відсутніх на видобутку сімей гномів.Потім зчитується рівно K різних невід’ємних цілих чисел – номери сімей, у довільному порядку, що не прийшли на видобуток. Кожне число не перевищує N.Програма Coop виводить на клавіатуру (стандартний пристрій виведення) єдине ціле число – кількість досяжних висот.
Система оцінки. 30% балів припадає на тести, в яких N, K ≤ min{N, 1000}. Ще 40% балів припадає на тести, в яких N ≤ 109, K ≤ min{N, 500}.
Приклад вхідних та вихідних даних:
Введення 1 Виведення 1
6 2 9
3 6
Введення 2 Виведення 2
5 3 3
2 3 4
Введення 3 Виведення 3
10 4 15
2 3 4 5