Сережа решил срочно купить новый моноблок. Сейчас он использует 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]\).
Примечание
После первого запроса массив \(a\) равен \([1, 2, 2, 4, 5]\), ответ равен \(29\), потому что подрезки массива можно разбить на блоки:
- \([1; 1]\): \([1]\), 1 блок;
- \([1; 2]\): \([1] + [2]\), 2 блока;
- \([1; 3]\): \([1] + [2, 2]\), 2 блока;
- \([1; 4]\): \([1] + [2, 2] + [4]\), 3 блока;
- \([1; 5]\): \([1] + [2, 2] + [4] + [5]\), 4 блока;
- \([2; 2]\): \([2]\), 1 блок;
- \([2; 3]\): \([2, 2]\), 1 блок;
- \([2; 4]\): \([2, 2] + [4]\), 2 блока;
- \([2; 5]\): \([2, 2] + [4] + [5]\), 3 блока;
- \([3; 3]\): \([2]\), 1 блок;
- \([3; 4]\): \([2] + [4]\), 2 блока;
- \([3; 5]\): \([2] + [4] + [5]\), 3 блока;
- \([4; 4]\): \([4]\), 1 блок;
- \([4; 5]\): \([4] + [5]\), 2 блока;
- \([5; 5]\): \([5]\), 1 блок;
что в сумме равняется
\(1 + 2 + 2 + 3 + 4 + 1 + 1 + 2 + 3 + 1 + 2 + 3 + 1 + 2 + 1 = 29\).