0190. Шары кругом

Input file name: input.txt
Output file name: output.txt
Time limit: 250 ms
Memory limit: 16 megabytes

Мальчик Петя любит играть с шарами. У него много разных шаров, и он составляет из них разные узоры. Однажды, он выложил N шаров по окружности. Теперь его очень интересует вопрос, сколько способов выбрать K подряд идущих шаров так, чтобы они все были разного цвета. Помогите, пожалуйста, Пете.

Формат входного файла

В первой строке записаны целые числа N и K (1 ≤ K ≤ N ≤ 60000). Во второй строке записаны N чисел - цвета шаров на окружности. Шары перечислены, начиная с ближайшего к Петиному столу, по часовой стрелке. Цвет указан в формате RGB, т.е. числом от 0 до 224-1.

Формат выходного файла

Выведите ответ на задачу.

Пример:

input.txtoutput.txt
10 3 0 1 2 0 2 1 3 4 0 2 8


Source: Petrozavodsk Winter 2003. SaratovSU #3 Training Contest, Wednesday, February 05

Discuss       Submit a solution



Printable version