Задача №114863. Стрит
Начинается турнир по обобщенному покеру! В турнире используется специальная колода. В неё входят карты, на которых написаны числа от \(1\) до \(n\). При этом с каждым числом в колоде есть бесконечно много карт.
В обобщенном покере используется только одна комбинация: стрит, которая представляет собой последовательность из \(m\) карт, на которых написаны последовательные числа: \(i, i+1, \ldots, i+m-1\). По правилам турнира у каждого из игроков в руке находятся \(s\) карт, а на стол выкладывается \(m\) карт. Каждый игрок пытается выбрать из \(s+m\) карт, которые он видит, \(m\) таких, чтобы они образовывали стрит.
Вы пришли на покер в качестве зрителя, поэтому видите только карты, лежащие на столе. Вам стало интересно, сколько различных стритов может получиться у игроков. Два стрита называются различными, если они начинаются с разной карты, иначе говоря, значения \(i\) в определении выше у них различны.
В первой строке дано три числа \(n\), \(m\) и \(s\) (\(1 \le n \le 10^9\); \(1 \le s < m \le 10^5\)) — максимальное значение карты, количество карт в столе и в руке соответственно.
Во второй строке дано \(m\) чисел, каждое из которых лежит в диапазоне от \(1\) до \(n\) — значения карт на столе.
Выведите количество различных возможных стритов, которые могут получиться у игроков.
В первом примере у игроков могут получиться стриты, начинающиеся с \(1\), \(2\), \(3\), \(4\) и \(5\).
10 5 2 7 1 3 5 6
5
11 6 2 5 5 5 5 5 5
0