Задача №111645. Массовый прогноз

Олимпиада завершена. Режим дорешивания.

В выборах председателя школьного клуба информатиков участвуют K кандидатов и N избирателей. Кандидаты пронумерованы от 1 до K, избиратели — от 1 до N.

По результатам голосования составляется список, i-й элемент этого списка равен номеру кандидата, за которого проголосовал i-й избиратель. Для каждого отрезка списка назначается наблюдатель, который подсчитывает голоса на этом отрезке. Таким образом, на выборах работают N(N + 1) / 2 наблюдателей.

Если наблюдатель обнаружит кандидата, набравшего на его отрезке более половины голосов, он публикует в социальной сети прогноз о том, что этот кандидат победит в выборах.

Требуется написать программу, которая по списку голосов определяет количество опубликованных наблюдателями прогнозов.

Входные данные

Первая строка входного файла содержит два числа N и K (1 ≤ N ≤ 500 000, 1 ≤ K ≤ 500 000). Вторая строка содержит N чисел V1, V2, ..., VN — список голосов избирателей (1 ≤ Vi ≤ K).

Выходные данные

Выходной файл должен содержать единственное число — количество прогнозов.

Примечание

Для окончательной проверки решений этой задачи используются 50 тестов. Тесты оцениваются независимо. Каждый тест оценивается в 2 балла. Значения N и K в тестах приведены в таблице.

Тест N K Тест N K Тест N K
1 2 2 18 2000 20 35 90000 1000
2 3 1 19 3000 2000 36 100000 5000
3 5 5 20 5000 2000 37 125000 1
4 10 10 21 7500 200 38 150000 12000
5 20 2 22 10000 10000 39 150000 18
6 30 3 23 15000 1500 40 200000 42000
7 50 20 24 20000 10 41 250000 26000
8 75 75 25 25000 100 42 300000 10000
9 100 2000 26 30000 15 43 350000 102000
10 150 30 27 35000 35 44 400000 12000
11 200 50 28 40000 10000 45 450000 5000
12 300 10 29 45000 10000 46 500000 2
13 400 100 30 50000 10000 47 500000 102000
14 500 2 31 55000 13000 48 500000 102000
15 300 200 32 60000 174 49 500000 102000
16 1000 2000 33 70000 10000 50 500000 501
17 1500 100 34 80000 1000      

Примеры
Входные данные
5 2
1 2 1 2 1
Выходные данные
9
Входные данные
3 7
5 2 6
Выходные данные
3
Сдать: для сдачи задач необходимо войти в систему