Сережа решил срочно купить новый моноблок. Сейчас он использует VPN и поэтому, чтобы попасть на сайт, надо решить вот такую капчу.

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

Например, крутость массива

• $$$[1, 1, 1]$$$ это $$$1$$$;
• $$$[5, 7]$$$ это $$$2$$$, ведь его можно разбить на два блока: $$$[5]$$$ и $$$[7]$$$;
• $$$[1, 7, 7, 7, 7, 7, 7, 7, 9, 9, 9, 9, 9, 9, 9, 9, 9]$$$ это 3, потому что его можно разбить на блоки $$$[1]$$$, $$$[7, 7, 7, 7, 7, 7, 7]$$$ и $$$[9, 9, 9, 9, 9, 9, 9, 9, 9]$$$.

Вам дан массив $$$a$$$ длины $$$n$$$, а также $$$m$$$ запросов, состоящих из двух целых чисел $$$i$$$ и $$$x$$$. Запрос $$$i$$$, $$$x$$$ означает, что теперь $$$i$$$-й элемент массива $$$a$$$ равен $$$x$$$.

После каждого запроса выведите сумму крутостей всех непустых подотрезков массива $$$a$$$. Другими словами, после каждого запроса вам надо вычислять $$$$$$\sum\limits_{l = 1}^n \sum\limits_{r = l}^n g(l, r),$$$$$$ где $$$g(l, r)$$$ это крутость массива $$$b = [a_l, a_{l + 1}, \ldots, a_r]$$$.