| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 35 | 13 | 7 | 46.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 |
5 2 1 2 1 2 1
9
3 7 5 2 6
3