Вдоль проспекта стоит N зданий, в двух из которых планируют открыть два ресторана быстрого питания - “Бургер Кинг” и ”KFC”. Необходимо спланировать расположение данных ресторанов таким образом, чтобы минимизировать конкуренцию между ними, для чего нужно разместить их в двух зданиях так, чтобы расстояние между ними превышало контрольное значение K. Определите, сколькими способами можно разместить рестораны.
Входные данные
Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит натуральное число K ( 2 ≤ K≤ 100 000 000) – минимальное расстояние между ресторанами, а во второй – количество зданий, стоящих вдоль проспекта N (1 ≤ N ≤ 10 000 000, N <, K). В каждой из следующих N строк находится одно целое число, не превышающее 5 000 000 000, обозначающее расстояние от начала проспекта до текущего здания. Данные отсортированы в порядке неубывания.
Запишите в ответе два числа: сначала значение искомой величины для файла А, затем – для файла B.
Типовой пример организации данных во входном файле
5
6
6
9
10
10
12
15
При таких исходных данных рестораны можно разместить 6 способами: {6, 12}, {6, 15}, {9, 15}, {12, 6}, {15, 6} и {15, 9).
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
