В этот раз Берляндская командная олимпиада по информатике проводится в отдалённом городке, куда ходит лишь один небольшой автобус. В нём есть n пассажирских мест, каждое из которых занято за одним из участвующих городов, то есть место i может занять только участник из города ai.
Сегодня автобус сделал m рейсов, каждый раз привозя n участников. Участников выстроили в очередь в порядке прибытия, люди из одного автобуса встают в очередь в том порядке, в котором они занимали места в автобусе. Так, если мы выпишем города, из которых прибыли участники в очереди, мы получим последовательность a1, a2, ..., an, повторенную m раз.
После прибытия всех рейсов участники начинают объединяться в команды. Если в очереди стоят k человек подряд из одного города, они собирают команду и выходят из очереди. Команды образовываются в произвольном порядке, пока есть k человек подряд из одного города.
Помогите организаторам определить, сколько участников будет находиться в очереди после того, как все команды уйдут из очереди. Можно доказать, что ответ не зависит от порядка, в котором образуются команды.