Stanley has decided to buy a new desktop PC made by the company "Monoblock", and to solve captcha on their website, he needs to solve the following task.

The awesomeness of an array is the minimum number of blocks of consecutive identical numbers in which the array could be split. For example, the awesomeness of an array

$[1, 1, 1]$ is $1$;

$[5, 7]$ is $2$, as it could be split into blocks $[5]$ and $[7]$;

$[1, 7, 7, 7, 7, 7, 7, 7, 9, 9, 9, 9, 9, 9, 9, 9, 9]$ is 3, as it could be split into blocks $[1]$, $[7, 7, 7, 7, 7, 7, 7]$, and $[9, 9, 9, 9, 9, 9, 9, 9, 9]$.

You are given an array $a$ of length $n$. There are $m$ queries of two integers $i$, $x$. A query $i$, $x$ means that from now on the $i$-th element of the array $a$ is equal to $x$.

After each query print the sum of awesomeness values among all subsegments of array $a$. In other words, after each query you need to calculate $$\sum\limits_{l = 1}^n \sum\limits_{r = l}^n g(l, r),$$ where $g(l, r)$ is the awesomeness of the array $b = [a_l, a_{l + 1}, \ldots, a_r]$.


-----Input-----

In the first line you are given with two integers $n$ and $m$ ($1 \leq n, m \leq 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the array $a$.

In the next $m$ lines you are given the descriptions of queries. Each line contains two integers $i$ and $x$ ($1 \leq i \leq n$, $1 \leq x \leq 10^9$).


-----Output-----

Print the answer to each query on a new line.


-----Examples-----

Input
5 5
1 2 3 4 5
3 2
4 2
3 1
2 1
2 2
Output
29
23
35
25
35


-----Note-----

After the first query $a$ is equal to $[1, 2, 2, 4, 5]$, and the answer is $29$ because we can split each of the subsegments the following way:

$[1; 1]$: $[1]$, 1 block;

$[1; 2]$: $[1] + [2]$, 2 blocks;

$[1; 3]$: $[1] + [2, 2]$, 2 blocks;

$[1; 4]$: $[1] + [2, 2] + [4]$, 3 blocks;

$[1; 5]$: $[1] + [2, 2] + [4] + [5]$, 4 blocks;

$[2; 2]$: $[2]$, 1 block;

$[2; 3]$: $[2, 2]$, 1 block;

$[2; 4]$: $[2, 2] + [4]$, 2 blocks;

$[2; 5]$: $[2, 2] + [4] + [5]$, 3 blocks;

$[3; 3]$: $[2]$, 1 block;

$[3; 4]$: $[2] + [4]$, 2 blocks;

$[3; 5]$: $[2] + [4] + [5]$, 3 blocks;

$[4; 4]$: $[4]$, 1 block;

$[4; 5]$: $[4] + [5]$, 2 blocks;

$[5; 5]$: $[5]$, 1 block;

which is $1 + 2 + 2 + 3 + 4 + 1 + 1 + 2 + 3 + 1 + 2 + 3 + 1 + 2 + 1 = 29$ in total.

Difficulty: MEDIUM_HARD
Tags: Mathematics

Combinatorics

Data structures

Implementation
Skill types: Data structures

Starter code:

Solutions:
import sys
input = sys.stdin.readline

def solve():
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	dp = ans = 1
	for i in range(1, n):
		dp += 1 if arr[i - 1] == arr[i] else i + 1
		ans += dp
	for _ in range(m):
		(i, x) = map(int, input().split())
		i -= 1
		if arr[i] == x:
			print(ans)
		else:
			if i > 0:
				if arr[i - 1] == arr[i]:
					ans += i * (n - i)
				elif x == arr[i - 1]:
					ans -= i * (n - i)
			if i < n - 1:
				if arr[i + 1] == arr[i]:
					ans += (i + 1) * (n - i - 1)
				elif x == arr[i + 1]:
					ans -= (i + 1) * (n - i - 1)
			print(ans)
			arr[i] = x
	return
solve()


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
pre = [0] * (n - 1)
ans = n * (n + 1) // 2
res = []
for i in range(n - 1):
	if a[i] != a[i + 1]:
		pre[i] = (i + 1) * (n - i - 1)
		ans += pre[i]
for j in range(m):
	(i, x) = map(int, input().split())
	i -= 1
	if x != a[i]:
		if i > 0 and a[i] == a[i - 1] and (x != a[i]):
			pre[i - 1] = i * (n - i)
			ans += pre[i - 1]
		elif i > 0 and a[i] != a[i - 1] and (x == a[i - 1]):
			ans -= pre[i - 1]
			pre[i - 1] = 0
		if i < n - 1 and a[i] == a[i + 1] and (x != a[i + 1]):
			pre[i] = (i + 1) * (n - i - 1)
			ans += pre[i]
		elif i < n - 1 and a[i] != a[i + 1] and (x == a[i + 1]):
			ans -= pre[i]
			pre[i] = 0
		a[i] = x
	res.append(ans)
print('\n'.join([str(i) for i in res]))


import sys
input = sys.stdin.readline
print = sys.stdout.write
(n, q) = map(int, input().split())
lst = list(map(int, input().split()))
tiang = [0] * n
blocks = n * (n + 1) // 2
for i in range(1, n):
	if lst[i] != lst[i - 1]:
		tiang[i] = 1
		blocks += i * (n - i)
for Q in range(q):
	(i, val) = map(int, input().split())
	i -= 1
	lst[i] = val
	if i > 0:
		if lst[i - 1] != val:
			if tiang[i] != 1:
				tiang[i] = 1
				blocks += i * (n - i)
		elif lst[i - 1] == val:
			if tiang[i] != 0:
				tiang[i] = 0
				blocks -= i * (n - i)
	if i < n - 1:
		if lst[i + 1] != val:
			if tiang[i + 1] != 1:
				tiang[i + 1] = 1
				blocks += (i + 1) * (n - i - 1)
		elif lst[i + 1] == val:
			if tiang[i + 1] != 0:
				tiang[i + 1] = 0
				blocks -= (i + 1) * (n - i - 1)
	print(str(blocks))
	print('\n')


import sys
import math

def beauty(arr, n):
	dp = [0 for i in range(n)]
	dp[0] = 1
	(cur, l) = (arr[0], 1)
	for i in range(1, n):
		if arr[i] == cur:
			dp[i] = dp[i - 1] + 1
			l += 1
		else:
			cur = arr[i]
			l = 1
			dp[i] = dp[i - 1] + (i + 1)
	return sum(dp)
input = sys.stdin.readline()
(n, t) = map(int, input.split())
input = sys.stdin.readline()
arr = list(map(int, input.split()))
b = beauty(arr, n)
while t > 0:
	t -= 1
	input = sys.stdin.readline()
	(i, x) = map(int, input.split())
	i -= 1
	if arr[i] == x:
		print(b)
		continue
	if i > 0:
		if arr[i - 1] == arr[i]:
			b += (n - i) * i
		if x == arr[i - 1]:
			b -= (n - i) * i
	if i < n - 1:
		if arr[i] == arr[i + 1]:
			b += (n - i - 1) * (i + 1)
		if x == arr[i + 1]:
			b -= (n - i - 1) * (i + 1)
	print(b)
	arr[i] = x


import sys
input = sys.stdin.readline

def solve():
	(n, m) = map(int, input().split(' '))
	a = input().split()
	ans = 0
	prev = int(a[0])
	for (i, j) in enumerate(a):
		if i == 0:
			continue
		if int(j) != prev:
			ans += i * (n - i)
		prev = int(j)
	ans += n * (n + 1) // 2
	for q in range(m):
		(x, y) = map(int, input().split(' '))
		if x - 2 >= 0:
			if int(a[x - 2]) == int(a[x - 1]):
				if y != int(a[x - 1]):
					ans += (x - 1) * (n - x + 1)
			elif y == int(a[x - 2]):
				ans -= (x - 1) * (n - x + 1)
		if x < n:
			if int(a[x]) == int(a[x - 1]):
				if y != int(a[x - 1]):
					ans += x * (n - x)
			elif y == int(a[x]):
				ans -= x * (n - x)
		a[x - 1] = y
		print(ans)
solve()


import sys

def solve():
	inp = sys.stdin.readline
	(n, m) = map(int, inp().split())
	a = list(map(int, inp().split()))
	b = [int(a[i - 1] != a[i]) for i in range(1, n)]
	w = [(i + 1) * (n - i - 1) for i in range(n - 1)]
	r = n * (n + 1) // 2
	for i in range(n - 1):
		r += b[i] * w[i]
	for i in range(m):
		(i, x) = map(int, inp().split())
		a[i - 1] = x
		if i < n:
			r -= b[i - 1] * w[i - 1]
			b[i - 1] = int(a[i] != a[i - 1])
			r += b[i - 1] * w[i - 1]
		if i > 1:
			r -= b[i - 2] * w[i - 2]
			b[i - 2] = int(a[i - 1] != a[i - 2])
			r += b[i - 2] * w[i - 2]
		print(r)

def main():
	solve()
main()


import collections
import heapq
import sys
import math
import itertools
import bisect
from io import BytesIO, IOBase
import os

def values():
	return tuple(map(int, sys.stdin.readline().split()))

def inlst():
	return [int(i) for i in sys.stdin.readline().split()]

def inp():
	return int(sys.stdin.readline())

def inpstr():
	return sys.stdin.readline().strip()

def words():
	return [i for i in sys.stdin.readline().split()]

def chars():
	return list(sys.stdin.readline().strip())

def solve():
	(n, m) = values()
	l = inlst()
	s = set()
	tmp = l[0]
	tot = 0
	for i in range(1, n):
		if l[i] != tmp:
			s.add(i)
			tot += i * (n - i)
		tmp = l[i]
	tot += n * (n + 1) // 2
	for i in range(m):
		(ind, x) = values()
		if ind in s:
			s.remove(ind)
			tot -= ind * (n - ind)
		h = ind - 1
		if h in s:
			s.remove(h)
			tot -= h * (n - h)
		if ind < n and x != l[ind]:
			s.add(ind)
			tot += ind * (n - ind)
		if ind > 1 and x != l[ind - 2]:
			s.add(ind - 1)
			tot += (ind - 1) * (n - (ind - 1))
		l[ind - 1] = x
		print(tot)
solve()


import sys
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
sums = 0
for i in range(n):
	sums += (i + 1) * (i + 2) / 2
for i in range(1, n):
	if a[i] == a[i - 1]:
		sums -= i * (n - i)
for _ in range(m):
	if n == 1:
		print(1)
		continue
	(i, x) = list(map(int, input().split()))
	i -= 1
	if i > 0 and a[i] == a[i - 1]:
		sums += i * (n - i)
	if i < n - 1 and a[i] == a[i + 1]:
		sums += (i + 1) * (n - i - 1)
	if i > 0 and x == a[i - 1]:
		sums -= i * (n - i)
	if i < n - 1 and x == a[i + 1]:
		sums -= (i + 1) * (n - i - 1)
	a[i] = x
	print(int(sums))


(n, m) = list(map(int, input().split()))
arr = list(map(int, input().split()))
result = []
cut = [1]
for i in range(1, len(arr)):
	if arr[i] != arr[i - 1]:
		cut.append(1)
	else:
		cut.append(0)
sum = 0
for i in range(len(cut)):
	if cut[i] == 0:
		sum += n - i
		continue
	sum += cut[i] * (i + 1) * (n - i)
for j in range(m):
	(i, x) = list(map(int, input().split()))
	i = i - 1
	arr[i] = x
	if i > 0:
		if arr[i] != arr[i - 1]:
			if cut[i] != 1:
				sum += i * (n - i)
			cut[i] = 1
		else:
			if cut[i] != 0:
				sum -= i * (n - i)
			cut[i] = 0
	if i < n - 1:
		if arr[i + 1] != arr[i]:
			if cut[i + 1] != 1:
				sum += (i + 1) * (n - i - 1)
			cut[i + 1] = 1
		else:
			if cut[i + 1] != 0:
				sum -= (i + 1) * (n - i - 1)
			cut[i + 1] = 0
	result.append(sum)
list(map(print, result))


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
ans = n * (n + 1) // 2
for i in range(n):
	if i + 1 == n or a[i] != a[i + 1]:
		ans += (i + 1) * (n - i - 1)
while m > 0:
	(i, x) = map(int, input().split())
	i = i - 1
	if i > 0 and a[i] != a[i - 1]:
		ans -= i * (n - i)
	if i + 1 < n and a[i] != a[i + 1]:
		ans -= (i + 1) * (n - i - 1)
	a[i] = x
	if i > 0 and a[i] != a[i - 1]:
		ans += i * (n - i)
	if i + 1 < n and a[i] != a[i + 1]:
		ans += (i + 1) * (n - i - 1)
	print(ans)
	m = m - 1


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
if n == 1:
	print('1\n' * m)
else:
	ans = (n + 1) * n // 2
	for i in range(n - 1):
		if arr[i] != arr[i + 1]:
			ans += (i + 1) * (n - i - 1)
	for q in range(m):
		(i, x) = map(int, input().split())
		i -= 1
		if arr[i] != x:
			if i != n - 1:
				(a, b) = arr[i:i + 2]
				pre = (i + 1) * (n - i - 1) if a != b else 0
				a = x
				cur = (i + 1) * (n - i - 1) if a != b else 0
				ans += cur - pre
			if i != 0:
				(a, b) = arr[i - 1:i + 1]
				pre = i * (n - i) if a != b else 0
				b = x
				cur = i * (n - i) if a != b else 0
				ans += cur - pre
		arr[i] = x
		print(ans)


(n, m) = map(int, input().split())
list1 = list(map(int, input().split()))
ans = n * (n + 1) // 2
for i in range(1, len(list1)):
	if list1[i] != list1[i - 1]:
		ans += i * (n - i)
res = []
for j in range(m):
	(y, x) = map(int, input().split())
	y -= 1
	if y >= 1 and list1[y] != list1[y - 1]:
		ans -= y * (n - y)
	if y < n - 1 and list1[y] != list1[y + 1]:
		ans -= (y + 1) * (n - y - 1)
	list1[y] = x
	if y >= 1 and list1[y] != list1[y - 1]:
		ans += y * (n - y)
	if y < n - 1 and list1[y] != list1[y + 1]:
		ans += (y + 1) * (n - y - 1)
	res.append(ans)
print(*res, sep='\n')


(n, m) = map(int, input().split())
arr = list(map(int, input().split()))

def work(sum, i, p):
	if i - 1 >= 0 and arr[i] != arr[i - 1]:
		sum += p * i * (n - i)
	if i + 1 < n and arr[i + 1] != arr[i]:
		sum += p * (i + 1) * (n - i - 1)
	return sum
sum = n * (n + 1) // 2
res = []
for i in range(1, n):
	if arr[i] != arr[i - 1]:
		sum += i * (n - i)
for w in range(m):
	(i, x) = map(int, input().split())
	i -= 1
	sum = work(sum, i, -1)
	arr[i] = x
	sum = work(sum, i, 1)
	res.append(sum)
print(*res, sep='\n')