Массовый прогноз

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

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

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

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

Первая строка входного файла содержит два числа $N$ и $K$ ($1 \le N \le 500\\,000$, $1 \le K \le 500\\,000$). Вторая строка содержит $N$ чисел $V\_1, V\_2, \ldots, V\_N$ --- список голосов избирателей ($1 \le V\_i \le K$).

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