Послідовна мелодія#12997

Послідовна мелодія

2 seconds
512 megabytes
Hard

Дядечко Пекос складає нову кантрі-пісню. Її мелодія записана як послідовність нот, кожна з яких представлена цілим числом від до включно.

На жаль, частина нот розмазалася — тепер їхні значення невідомі. Послідовність нот називається послідовною, якщо кожна нота (крім першої) рівно на більша за попередню, а всі ноти мають значення від до .

Скількома різними способами дядечко Пекос може вибрати фрагмент своєї мелодії та заповнити пропущені ноти так, щоб цей фрагмент став послідовним?

Input

У першому рядку задано два цілі числа та — довжина мелодії та максимальне можливе значення ноти відповідно.

У другому рядку задано цілих чисел a_i — ноти мелодії, де a_i = -1 означає невідому ноту, а невід’ємне значення a_i відповідає відомій ноті.

1 \le n, k \le 10^6,

-1 \le a_i \le k.

Output

Виведіть одне ціле число — кількість різних способів вибрати підмасив і заповнити пропущені ноти так, щоб мелодія стала послідовною.

Examples

Example

Loading
Loading

Note

Існує різних способів отримати послідовний підмасив.

  • спосіб: вибрати лише першу ноту.

  • способів: вибрати лише другу ноту та присвоїти їй будь-яке значення від до .

  • спосіб: вибрати лише третю ноту.

  • спосіб: вибрати першу та другу ноти і присвоїти другій ноті значення .

  • спосіб: вибрати другу та третю ноти і присвоїти другій ноті значення .