C. Моноблок
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сережа решил срочно купить новый моноблок. Сейчас он использует 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]$$$.

Входные данные

В первой строке вводятся $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — массив $$$a$$$.

В каждой из следующих $$$m$$$ строк вам дает описание запросов. Каждая строка содержит два целых числа $$$i$$$ и $$$x$$$ ($$$1 \leq i \leq n$$$, $$$1 \leq x \leq 10^9$$$).

Выходные данные

После каждого запроса выведите ответ на задачу в отдельной строке.

Пример
Входные данные
5 5
1 2 3 4 5
3 2
4 2
3 1
2 1
2 2
Выходные данные
29
23
35
25
35
Примечание

После первого запроса массив $$$a$$$ равен $$$[1, 2, 2, 4, 5]$$$, ответ равен $$$29$$$, потому что подрезки массива можно разбить на блоки:

  1. $$$[1; 1]$$$: $$$[1]$$$, 1 блок;
  2. $$$[1; 2]$$$: $$$[1] + [2]$$$, 2 блока;
  3. $$$[1; 3]$$$: $$$[1] + [2, 2]$$$, 2 блока;
  4. $$$[1; 4]$$$: $$$[1] + [2, 2] + [4]$$$, 3 блока;
  5. $$$[1; 5]$$$: $$$[1] + [2, 2] + [4] + [5]$$$, 4 блока;
  6. $$$[2; 2]$$$: $$$[2]$$$, 1 блок;
  7. $$$[2; 3]$$$: $$$[2, 2]$$$, 1 блок;
  8. $$$[2; 4]$$$: $$$[2, 2] + [4]$$$, 2 блока;
  9. $$$[2; 5]$$$: $$$[2, 2] + [4] + [5]$$$, 3 блока;
  10. $$$[3; 3]$$$: $$$[2]$$$, 1 блок;
  11. $$$[3; 4]$$$: $$$[2] + [4]$$$, 2 блока;
  12. $$$[3; 5]$$$: $$$[2] + [4] + [5]$$$, 3 блока;
  13. $$$[4; 4]$$$: $$$[4]$$$, 1 блок;
  14. $$$[4; 5]$$$: $$$[4] + [5]$$$, 2 блока;
  15. $$$[5; 5]$$$: $$$[5]$$$, 1 блок;
что в сумме равняется $$$1 + 2 + 2 + 3 + 4 + 1 + 1 + 2 + 3 + 1 + 2 + 3 + 1 + 2 + 1 = 29$$$.