Послідовний фрагмент повністю визначається своїм першим значенням : на позиції фрагмента [l, r] стоїть v + (i - l). Тому зручно ввести d_i = a_i - i для кожної відомої ноти.
Розглянемо два види фрагментів окремо.
Фрагмент містить хоча б одну відому ноту. Тоді визначено однозначно першою ж відомою нотою, а всі інші відомі ноти фрагмента мають давати те саме . Отже фрагмент [l, r] підходить тоді й лише тоді, коли всі відомі ноти в ньому мають однакове , і виконано d + l \ge 0 та d + r \le k (перша й остання ноти лежать у , а решта — між ними). Для фіксованого нехай — перша відома нота праворуч, а — позиція перед першою відомою нотою з іншим . Тоді підходять рівно ті , що f \le r \le \min(R,\ k - d) — це один доданок за .
Фрагмент складається лише з невідомих нот. Для довжини підходить будь-яке з 0 \le v та v + L - 1 \le k, тобто \max(0,\ k - L + 2) способів. У блоці невідомих довжини є M - L + 1 фрагментів довжини , тож блок дає \sum_{L=1}^{M} (M - L + 1)\max(0, k - L + 2).
Обидві частини рахуються одним проходом; масиви «перша відома праворуч» та «перша відома з іншим » будуються проходом справа наліво. Відповідь може сягати приблизно 3 \cdot 10^{17}, тож потрібен 64-бітний тип.
Складність: .
Для цього етапу офіційного розбору опубліковано не було; цей текст написано для архіву за розв'язком, який перевірено на задачі.