시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB3513746.667%

문제

В выборах председателя школьного клуба информатиков участвуют $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$).

출력

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

채점

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

В этой задаче результаты окончательной проверки во время тура недоступны.

Тест ${\mathbf N }$ ${\mathbf K}$ Тест ${\mathbf N }$ ${\mathbf K}$ Тест ${\mathbf N }$ ${\mathbf 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      

예제 입력 1

5 2
1 2 1 2 1

예제 출력 1

9

예제 입력 2

3 7
5 2 6

예제 출력 2

3

채점 및 기타 정보

  • 50개 이상의 데이터를 맞아야 를 받는다.
  • 예제는 채점하지 않는다.