André é um maratonista do CIn-UFPE. Todo sábado, durante os treinos, ele come de tudo: salgadinho, refrigerante, biscoito, água e mentos. Principalmente mentos. Mas o problema, porém, é que toda vez que André vai tirar alguns mentos do tubo, ele tem que parar de codar por alguns instantes, o que atrapalha sua concentração.

O mentos vem em um tubo com duas pontas. Cada vez que André quer chupar alguns, ele escolhe um certo sabor, e olha pra cada ponta do mentos. Em cada uma, se houver um mentos do sabor escolhido, ele pega. Se não houver nenhum daquele sabor nas pontas, ele não pega nenhum, e só parou de codar à toa. Para diminuir a perda de tempo durante o contest, André decidiu minimizar suas paradas para pegar mentos. Ele fez um corte fino ao longo do tubo, para poder ver com antecedência quais sabores tem dentro dele. Mas ele não vai pegar do meio, e fez isso apenas para poder decidir melhor quais sabores irá escolher tirar das pontas em cada uma de suas paradas.

Agora, André precisa calcular o número mínimo de vezes que ele deve parar para pegar seus mentos, seguindo o método descrito, até eles acabarem. Ele calcularia isso facilmente usando Transformada de Fourier, mas ele está ocupado codando uma questão. Por isso cabe a você, um companheiro de time dele, fazer isso para ajudá-lo.