Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef calls a sequence *good* if it does not contain any two adjacent identical elements.

Initially, Chef has a sequence $a_{1}, a_{2}, \ldots, a_{N}$. He likes to change the sequence every now and then. You should process $Q$ queries. In each query, Chef chooses an index $x$ and changes the $x$-th element of the sequence to $y$. After each query, can you find the length of the longest good subsequence of the current sequence?

Note that the queries are not independent.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $Q$.
The second line contains $N$ space-separated integers $a_{1}, a_{2}, \ldots, a_{N}$.
$Q$ lines follow. Each of these lines contains two space-separated integers $x$ and $y$ describing a query.

------  Output ------
After each query, print a single line containing one integer ― the length of the longest good subsequence.

------  Constraints ------
$1 ≤ T ≤ 5$
$1 ≤ N, Q ≤ 10^{5}$
$1 ≤ a_{i} ≤ 10^{9}$ for each valid $i$
$1 ≤ x ≤ N$
$1 ≤ y ≤ 10^{9}$

------  Subtasks ------
Subtask #1 (35 points): $Q = 1$

Subtask #2 (65 points): original constraints

----- Sample Input 1 ------ 
1

5 2

1 1 2 5 2

1 3

4 2
----- Sample Output 1 ------ 
5

3

Difficulty: HARD
Tags: Ad-hoc

Starter code:

Solutions:
tc = int(input())
while tc > 0:
	(n, q) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	currlen = 1
	i = 1
	while i < n:
		if arr[i] != arr[i - 1]:
			currlen += 1
		else:
			while i < n and arr[i] == arr[i - 1]:
				i += 1
			if i < n:
				currlen += 1
		i += 1
	while q > 0:
		(x, y) = map(int, input().split())
		if arr[x - 1] == y:
			print(currlen)
		else:
			p = ne = 0
			p += 1 if x - 1 > 0 and arr[x - 1] != arr[x - 2] else 0
			p += 1 if x - 1 < n - 1 and arr[x - 1] != arr[x] else 0
			arr[x - 1] = y
			ne += 1 if x - 1 > 0 and arr[x - 1] != arr[x - 2] else 0
			ne += 1 if x - 1 < n - 1 and arr[x - 1] != arr[x] else 0
			currlen = currlen - p + ne
			print(currlen)
		q -= 1
	tc -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 1
	for i in range(1, n):
		if a[i] == a[i - 1]:
			continue
		ans += 1
	for t in range(k):
		(pos, val) = map(int, input().split())
		pos -= 1
		if a[pos] == val:
			print(ans)
			continue
		if n == 1:
			print(1)
			continue
		if pos == 0:
			if a[pos] == a[pos + 1]:
				ans += 1
			elif val == a[pos + 1]:
				ans -= 1
		elif pos == n - 1:
			if a[pos] == a[pos - 1]:
				ans += 1
			elif val == a[pos - 1]:
				ans -= 1
			else:
				ans += 0
		elif a[pos] == a[pos - 1]:
			ans += 1
			if a[pos] == a[pos + 1]:
				ans += 1
			elif val == a[pos + 1]:
				ans -= 1
		elif val == a[pos - 1]:
			ans -= 1
			if a[pos] == a[pos + 1]:
				ans += 1
			elif val == a[pos + 1]:
				ans -= 1
		elif a[pos] == a[pos + 1]:
			ans += 1
		elif val == a[pos + 1]:
			ans -= 1
		a[pos] = val
		print(ans)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	initial = 1
	for i in range(1, n):
		if l[i] != l[i - 1]:
			initial += 1
	for i in range(q):
		(x, y) = map(int, input().split())
		if n == 1:
			print(1)
			continue
		x -= 1
		if l[x] == y:
			print(initial)
			continue
		if x == 0:
			if y == l[x + 1]:
				initial -= 1
			elif l[x] == l[x + 1]:
				initial += 1
		elif x == n - 1:
			if y == l[x - 1]:
				initial -= 1
			elif l[x] == l[x - 1]:
				initial += 1
		elif y == l[x - 1] == l[x + 1]:
			initial -= 2
		elif (y == l[x - 1] or y == l[x + 1]) and (l[x] == l[x - 1] or l[x] == l[x + 1]):
			initial = initial
		elif y == l[x - 1] or y == l[x + 1]:
			initial -= 1
		elif l[x] == l[x - 1] == l[x + 1]:
			initial += 2
		elif l[x] == l[x - 1] or l[x] == l[x + 1]:
			initial += 1
		print(initial)
		l[x] = y


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	length = 1
	for i in range(1, n):
		length += a[i] != a[i - 1]
	for i in range(q):
		(x, y) = map(int, input().split())
		x = x - 1
		if x != 0:
			length -= a[x] != a[x - 1]
			length += y != a[x - 1]
		if x != n - 1:
			length -= a[x] != a[x + 1]
			length += y != a[x + 1]
		a[x] = y
		print(length)


T = int(input())
for i in range(T):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	a = [0] * n
	if n == 1:
		print(1)
	else:
		ss = len(l)
		for i in range(n - 1):
			if l[i] == l[i + 1]:
				a[i + 1] = 1
		longest = ss - a.count(1)
		for i in range(q):
			(xx, b) = map(int, input().split())
			if xx == 1:
				l[xx - 1] = b
				if l[xx] == l[xx - 1]:
					if a[xx] == 0:
						longest -= 1
					a[xx] = 1
				else:
					if a[xx] == 1:
						longest += 1
					a[xx] = 0
				print(longest)
			elif xx == ss:
				l[xx - 1] = b
				if l[xx - 1] == l[xx - 2]:
					if a[xx - 1] == 0:
						longest -= 1
					a[xx - 1] = 1
				else:
					if a[xx - 1] == 1:
						longest += 1
					a[xx - 1] = 0
				print(longest)
			else:
				l[xx - 1] = b
				if l[xx - 1] == l[xx - 2]:
					if a[xx - 1] == 0:
						longest -= 1
					a[xx - 1] = 1
				else:
					if a[xx - 1] == 1:
						longest += 1
					a[xx - 1] = 0
				if l[xx] == l[xx - 1]:
					if a[xx] == 0:
						longest -= 1
					a[xx] = 1
				else:
					if a[xx] == 1:
						longest += 1
					a[xx] = 0
				print(longest)


for _ in range(int(input())):
	(lens, qry) = [int(x) for x in input().split()]
	arrs = [int(x) for x in input().split()]
	answer = 1
	for i in range(1, lens):
		if arrs[i] != arrs[i - 1]:
			answer += 1
	for _ in range(qry):
		(i, v) = [int(x) for x in input().split()]
		i -= 1
		if i == 0 or arrs[i] != arrs[i - 1]:
			answer -= 1
		if i + 1 < lens and arrs[i] != arrs[i + 1]:
			answer -= 1
		arrs[i] = v
		if i == 0 or arrs[i] != arrs[i - 1]:
			answer += 1
		if i + 1 < lens and arrs[i] != arrs[i + 1]:
			answer += 1
		print(answer)


import sys, math, itertools, random, bisect
from collections import defaultdict
INF = 10 ** 18

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, q) = get_ints()
	a = get_array()
	a = [-1] + a + [-1]
	ans = 2
	for i in range(1, n + 1):
		if a[i] != a[i - 1]:
			ans += 1
	for _ in range(q):
		(x, y) = get_ints()
		if a[x] == a[x - 1] and a[x] == a[x + 1]:
			if y != a[x]:
				ans += 2
		elif a[x] != a[x - 1] and a[x] == a[x + 1]:
			if y != a[x]:
				ans += 1
			if y == a[x - 1]:
				ans -= 1
		elif a[x] == a[x - 1] and a[x] != a[x + 1]:
			if y != a[x]:
				ans += 1
			if y == a[x + 1]:
				ans -= 1
		else:
			if y == a[x - 1]:
				ans -= 1
			if y == a[x + 1]:
				ans -= 1
		a[x] = y
		print(ans - 2)


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	count = 0
	for j in range(n - 1, 0, -1):
		if l[j] != l[j - 1]:
			count += 1
	for j in range(q):
		(x, y) = map(int, input().split())
		c = 0
		d = 0
		if x > 1:
			if l[x - 1] == l[x - 2]:
				c += 1
		if x < n:
			if l[x - 1] == l[x]:
				c += 1
		l[x - 1] = y
		if x > 1:
			if l[x - 1] == l[x - 2]:
				d += 1
		if x < n:
			if l[x - 1] == l[x]:
				d += 1
		count = count + c - d
		print(count + 1)


t = int(input())
for _ in range(t):
	(n, q) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	c = 1
	for i in range(q):
		(x, y) = list(map(int, input().split()))
		p = a[x - 1]
		if i == 0:
			a[x - 1] = y
			for i in range(n - 1):
				if a[i] != a[i + 1]:
					c += 1
		else:
			a[x - 1] = y
			if x == 1:
				if a[x - 1] == a[x]:
					c -= 1
			elif x == n:
				if a[x - 1] == a[x - 2]:
					c -= 1
			else:
				if a[x - 1] == a[x]:
					c -= 1
				if a[x - 1] == a[x - 2]:
					c -= 1
			if x == 1:
				if p == a[x]:
					c += 1
			elif x == n:
				if p == a[x - 2]:
					c += 1
			else:
				if p == a[x]:
					c += 1
				if p == a[x - 2]:
					c += 1
		print(c)


for t in range(int(input())):
	(n, q) = map(int, input().split())
	store = list(map(int, input().split()))
	curr_long = 1
	for i in range(1, n):
		if store[i] != store[i - 1]:
			curr_long += 1
	for z in range(q):
		(x, y) = map(int, input().split())
		x -= 1
		initial = 0
		changed = 0
		if x > 0 and store[x] != store[x - 1]:
			initial += 1
		if x < n - 1 and store[x] != store[x + 1]:
			initial += 1
		store[x] = y
		if x > 0 and store[x] != store[x - 1]:
			changed += 1
		if x < n - 1 and store[x] != store[x + 1]:
			changed += 1
		curr_long = curr_long - initial + changed
		print(curr_long)


t = int(input())
for j in range(t):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	good = 1
	for i in range(1, n):
		if l[i] != l[i - 1]:
			good += 1
	for i in range(q):
		(x, y) = map(int, input().split())
		x = x - 1
		if x > 0 and l[x] != l[x - 1]:
			good -= 1
		if x < n - 1 and l[x] != l[x + 1]:
			good -= 1
		l[x] = y
		if x > 0 and l[x] != l[x - 1]:
			good += 1
		if x < n - 1 and l[x] != l[x + 1]:
			good += 1
		print(good)


try:
	t = int(input())
	for _ in range(t):
		(n, q) = map(int, input().split())
		l = list(map(int, input().split()))
		length = 1
		for i in range(1, n):
			length += l[i] != l[i - 1]
		for i in range(q):
			(x, y) = map(int, input().split())
			x = x - 1
			if x != 0:
				length -= l[x] != l[x - 1]
				length += y != l[x - 1]
			if x != n - 1:
				length -= l[x] != l[x + 1]
				length += y != l[x + 1]
			l[x] = y
			print(length)
except EOFError as t:
	pass


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	a = list(input().split())
	loc = [0] * n
	rank = 0
	for i in range(n):
		if i > 0 and a[i] != a[i - 1]:
			rank += 1
			loc[i] = rank
		else:
			loc[i] = rank
	c = rank + 1
	for _ in range(q):
		(x, y) = map(int, input().split())
		x -= 1
		y = str(y)
		if a[x] != y:
			if x > 0 and (a[x] == a[x - 1] and y != a[x - 1]):
				c += 1
			if x > 0 and (a[x] != a[x - 1] and y == a[x - 1]):
				c -= 1
			if x < n - 1 and (a[x] != a[x + 1] and y == a[x + 1]):
				c -= 1
			if x < n - 1 and (a[x] == a[x + 1] and y != a[x + 1]):
				c += 1
			a[x] = y
		print(c)


for _ in range(int(input())):
	(n, q) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	x = 1
	for j in range(n - 1):
		if l[j + 1] == l[j]:
			continue
		else:
			x = x + 1
	if n > 1:
		for k in range(q):
			(i, v) = map(int, input().split())
			if l[i - 1] == v:
				print(x)
				continue
			if i == 1 or i == n:
				if i == 1:
					if l[i - 1] == l[i] and l[i] != v:
						x = x + 1
					elif l[i - 1] != l[i] and l[i] == v:
						x = x - 1
				elif i == n:
					if l[i - 1] == l[i - 2] and l[i - 2] != v:
						x = x + 1
					elif l[i - 1] != l[i - 2] and l[i - 2] == v:
						x = x - 1
				print(x)
				l[i - 1] = v
			else:
				if l[i - 1] == l[i - 2] == l[i]:
					if l[i - 1] != v:
						x = x + 2
				elif l[i] == l[i - 2] and l[i] != l[i - 1]:
					if v == l[i]:
						x = x - 2
				elif l[i] == l[i - 1] or l[i - 2] == l[i - 1]:
					if l[i] == l[i - 1]:
						if v == l[i - 2]:
							x = x + 0
						else:
							x = x + 1
					elif v == l[i]:
						x = x + 0
					else:
						x = x + 1
				elif l[i - 1] != l[i - 2] and l[i - 2] != l[i]:
					if v == l[i] or v == l[i - 2]:
						x = x - 1
				l[i - 1] = v
				print(x)
	else:
		for i in range(q):
			(x, y) = map(int, input().split())
			print(1)


try:
	test_case = int(input())
	while test_case:
		(length, q) = map(int, input().split())
		arr = list(map(int, input().split()))
		temp = length
		for i in range(1, length):
			temp -= arr[i] == arr[i - 1]
		while q:
			(x, y) = map(int, input().split())
			x -= 1
			if x != 0:
				temp -= arr[x] != arr[x - 1]
				temp += y != arr[x - 1]
			if length != x + 1:
				temp -= arr[x] != arr[x + 1]
				temp += y != arr[x + 1]
			print(temp)
			arr[x] = y
			q -= 1
		test_case -= 1
except:
	pass


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	count = 1
	start = a[0]
	i = 0
	while i < len(a) - 1:
		if a[i + 1] != start:
			count += 1
			start = a[i + 1]
		i += 1
	for _ in range(q):
		(x, y) = map(int, input().split())
		if n == 1:
			print(1)
		else:
			if x - 1 != 0 and x - 1 != len(a) - 1:
				c1 = 1
				j = 0
				b = a[x - 2:x + 1]
				s1 = b[0]
				while j < 2:
					if b[j + 1] != s1:
						c1 += 1
						s1 = b[j + 1]
					j += 1
			temp = a[x - 1]
			a[x - 1] = y
			if a[x - 1] == temp:
				print(count)
			elif x - 1 == 0 and temp == a[x]:
				count += 1
				print(count)
			elif x - 1 == 0 and temp != a[x]:
				if a[x - 1] == a[x]:
					count -= 1
					print(count)
				else:
					print(count)
			elif x - 1 == len(a) - 1 and temp == a[x - 2]:
				count += 1
				print(count)
			elif x - 1 == len(a) - 1 and temp != a[x - 2]:
				if a[x - 1] == a[x - 2]:
					count -= 1
					print(count)
				else:
					print(count)
			else:
				c2 = 1
				b1 = a[x - 2:x + 1]
				s2 = b1[0]
				k = 0
				while k < 2:
					if b1[k + 1] != s2:
						c2 += 1
						s2 = b1[k + 1]
					k += 1
				if c1 == c2:
					print(count)
				elif c1 > c2:
					c3 = c1 - c2
					count -= c3
					print(count)
				else:
					c3 = c2 - c1
					count += c3
					print(count)


for tt in range(int(input())):
	(n, q) = map(int, input().split())
	l = [-1] + list(map(int, input().split()))
	cnt = 0
	for i in range(1, n + 1):
		cnt += l[i] != l[i - 1]
	for k in range(q):
		(x, y) = map(int, input().split())
		if l[x] != l[x - 1]:
			cnt -= 1
		if x != n:
			if l[x + 1] != l[x]:
				cnt -= 1
		l[x] = y
		if l[x] != l[x - 1]:
			cnt += 1
		if x != n:
			if l[x + 1] != l[x]:
				cnt += 1
		print(cnt)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	count = 1
	for i in range(n - 1):
		if a[i] != a[i + 1]:
			count += 1
	for i in range(q):
		(x, y) = map(int, input().split())
		x -= 1
		if x != 0:
			if a[x] != a[x - 1]:
				count -= 1
			if y != a[x - 1]:
				count += 1
		if x != n - 1:
			if a[x] != a[x + 1]:
				count -= 1
			if y != a[x + 1]:
				count += 1
		a[x] = y
		print(count)


t = int(input())
for _ in range(t):
	(n, q) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	total = 1
	for i in range(1, n):
		total += arr[i] != arr[i - 1]
	for i in range(q):
		(x, y) = list(map(int, input().split()))
		x = x - 1
		if x != 0:
			total -= arr[x - 1] != arr[x]
			total += arr[x - 1] != y
		if x != n - 1:
			total -= arr[x + 1] != arr[x]
			total += arr[x + 1] != y
		arr[x] = y
		print(total)


def findmax(l, n):
	cnt = 1
	for i in range(1, n):
		if l[i] != l[i - 1]:
			cnt += 1
	return cnt

def panda(l, n, x, y, mx):
	x1 = l[x - 1]
	l[x - 1] = y
	if x == n and n != 1:
		if l[x - 2] != l[x - 1] and x1 == l[x - 2]:
			mx += 1
		elif l[x - 2] == l[x - 1] and x1 != l[x - 2]:
			mx -= 1
		return mx
	elif x == 1 and x != n:
		if l[x] != l[x - 1] and x1 == l[x]:
			mx += 1
		elif l[x] == l[x - 1] and x1 != l[x]:
			mx -= 1
		return mx
	elif x == 1 and x == n:
		return 1
	else:
		cnt = 0
		if l[x - 2] != l[x - 1]:
			cnt += 1
		if l[x] != l[x - 1]:
			cnt += 1
		if l[x - 2] != x1:
			cnt -= 1
		if l[x] != x1:
			cnt -= 1
	return mx + cnt
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	mx = findmax(l, n)
	for xx in range(q):
		(x, y) = map(int, input().split())
		mx = panda(l, n, x, y, mx)
		l[x - 1] = y
		print(mx)


for _ in range(int(input())):
	(n, queries) = map(int, input().split())
	seq = list(map(int, input().split()))
	if n == 1:
		for q in range(queries):
			print(1)
		break
	mx = 0
	last = 0
	for cur in seq:
		if cur != last:
			mx += 1
		last = cur
	for q in range(queries):
		(x, y) = map(int, input().split())
		idx = x - 1
		ori = seq[idx]
		l = seq[idx - 1] if idx else 0
		r = seq[idx + 1] if idx < n - 1 else 0
		seq[idx] = y
		if l == r:
			if ori == l:
				if y != l:
					mx += 2
			elif y == l:
				mx -= 2
		elif ori == l or ori == r:
			if y != l and y != r:
				mx += 1
		elif y == l or y == r:
			mx -= 1
		print(mx)


import sys
input = sys.stdin.readline
GI = lambda : int(input())
GIS = lambda : map(int, input().split())
LGIS = lambda : list(GIS())

def main():
	for t in range(GI()):
		(n, q) = GIS()
		xs = LGIS()
		count = 0
		for i in range(n):
			if i == 0 or xs[i - 1] != xs[i]:
				count += 1
		for _ in range(q):
			(i, y) = GIS()
			i -= 1
			x = xs[i]
			l = xs[i - 1] if i else 'left'
			r = xs[i + 1] if i < n - 1 else 'right'
			if x == y:
				pass
			elif l == x == r:
				count += 2
			elif l != x and x == r:
				if y != l:
					count += 1
			elif l == x and x != r:
				if y != r:
					count += 1
			elif l != x and x != r:
				if y == l and y == r:
					count -= 2
				elif y == l or y == r:
					count -= 1
			xs[i] = y
			print(count)
main()


import sys
import math
from collections import defaultdict, Counter
input = sys.stdin.readline

def print(x):
	sys.stdout.write(str(x) + '\n')
t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	l = []
	c = 1
	for j in range(1, n):
		if a[j] != a[j - 1]:
			l.append(c)
			c = 1
		else:
			c += 1
	l.append(c)
	prev = len(l)
	for j in range(q):
		(x, y) = map(int, input().split())
		if a[x - 1] == y or n == 1:
			print(prev)
			continue
		if x == 1:
			if a[x] == y:
				prev -= 1
			elif a[0] == a[x]:
				prev += 1
		elif x == n:
			if a[-2] == y:
				prev -= 1
			elif a[-1] == a[-2]:
				prev += 1
		else:
			if a[x - 2] == y:
				prev -= 1
			if a[x] == y:
				prev -= 1
			if a[x] == a[x - 1]:
				prev += 1
			if a[x - 1] == a[x - 2]:
				prev += 1
		a[x - 1] = y
		print(prev)


def initLength(s, n):
	length = 1
	if n == 1:
		return 1
	for x in range(1, n):
		if s[x] != s[x - 1]:
			length += 1
	return length

def calcLength(m, s, x, y, n):
	np = 0
	nc = 0
	if x != 0 and s[x] != s[x - 1]:
		np += 1
	if x != n - 1 and s[x] != s[x + 1]:
		np += 1
	s[x] = y
	if x != 0 and s[x] != s[x - 1]:
		nc += 1
	if x != n - 1 and s[x] != s[x + 1]:
		nc += 1
	return m - np + nc
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	s = list(map(int, input().split()))
	maxLength = initLength(s, n)
	for __ in range(q):
		(x, y) = map(int, input().split())
		x = x - 1
		maxLength = calcLength(maxLength, s, x, y, n)
		print(maxLength)
		s[x] = y


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	count = 1
	for i in range(1, n):
		if arr[i] != arr[i - 1]:
			count += 1
	for j in range(q):
		(x, y) = map(int, input().split())
		x = x - 1
		if x != n - 1:
			if arr[x] != arr[x + 1]:
				count -= 1
			if y != arr[x + 1]:
				count += 1
		if x != 0:
			if arr[x] != arr[x - 1]:
				count -= 1
			if y != arr[x - 1]:
				count += 1
		arr[x] = y
		print(count)


for _ in range(int(input())):
	(length, que) = map(int, input().split())
	arr = list(map(int, input().split()))
	previ = arr[0]
	count = 1
	for ind in range(1, length):
		if arr[ind] != previ:
			count += 1
			previ = arr[ind]
	for _ in range(que):
		(index, ele) = map(int, input().split())
		cn = 0
		nn = 0
		if index - 2 >= 0:
			if arr[index - 2] != arr[index - 1]:
				cn -= 1
			if arr[index - 2] != ele:
				cn += 1
		if index < length:
			if arr[index - 1] != arr[index]:
				cn -= 1
			if ele != arr[index]:
				cn += 1
		arr[index - 1] = ele
		count += cn
		print(count)


def good_contiguous_subsequence_length(numbers):
	repeat_count = 0
	repeating_indices = set()
	n = len(numbers)
	for index in range(n - 1):
		if index not in repeating_indices or index + 1 not in repeating_indices:
			if numbers[index] == numbers[index + 1]:
				repeat_count += 1
				repeating_indices.add(index)
				repeating_indices.add(index + 1)
	repeat_count = len(repeating_indices)
	if repeat_count == 0:
		return n
	elif repeat_count == n:
		return 1
	else:
		breakpoints = set()
		for value in repeating_indices:
			if value - 1 not in repeating_indices or value + 1 not in repeating_indices:
				breakpoints.add(value)
		breakpoints.add(0)
		breakpoints.add(n - 1)
		if numbers[-1] == numbers[-2]:
			breakpoints.remove(n - 1)
		if numbers[0] == numbers[1]:
			breakpoints.remove(0)
		breakpoints = sorted(breakpoints)
		if len(breakpoints) > 1:
			max_good_length = breakpoints[1] - breakpoints[0] + 1
			for point in range(1, len(breakpoints) - 1):
				if numbers[point] != numbers[point + 1]:
					max_good_length = max(max_good_length, breakpoints[point + 1] - breakpoints[point] + 1)
		elif breakpoints == 1:
			max_good_length = min(n, 3)
		else:
			max_good_length = 1
		return max_good_length

def good_subsequence_length(numbers):
	max_subsequence = []
	for value in numbers:
		if len(max_subsequence) < 1 or value != max_subsequence[-1]:
			max_subsequence.append(value)
	return len(max_subsequence)
for testcase in range(int(input())):
	(n, q) = list(map(int, input().split()))
	numbers_array = list(map(int, input().split()))
	current_good_subsequence_length = good_subsequence_length(numbers_array)
	for query in range(q):
		(x, y) = list(map(int, input().split()))
		if n == 1:
			print(n)
		else:
			if x > 1:
				if numbers_array[x - 2] != numbers_array[x - 1]:
					if numbers_array[x - 2] == y:
						current_good_subsequence_length -= 1
				elif numbers_array[x - 2] != y:
					current_good_subsequence_length += 1
			if x < n:
				if numbers_array[x - 1] != numbers_array[x]:
					if numbers_array[x] == y:
						current_good_subsequence_length -= 1
				elif numbers_array[x] != y:
					current_good_subsequence_length += 1
			print(current_good_subsequence_length)
		numbers_array[x - 1] = y


try:
	t = int(input())
	while t:
		(n, q) = map(int, input().split())
		l = list(map(int, input().split()))
		(count, previous) = (0, '')
		for i in range(n):
			if previous == l[i]:
				pass
			else:
				count += 1
				previous = l[i]
		while q:
			(x, y) = map(int, input().split())
			x = x - 1
			if x != 0:
				count -= l[x] != l[x - 1]
				count += y != l[x - 1]
			if x != n - 1:
				count -= l[x] != l[x + 1]
				count += y != l[x + 1]
			print(count)
			l[x] = y
			q -= 1
		t -= 1
except:
	pass


from sys import stdin, stdout
import math, sys, heapq
from itertools import permutations, combinations
from collections import defaultdict, deque, OrderedDict
from os import path
import random
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

	def I():
		return int(input())

	def In():
		return map(int, input().split())
else:

	def I():
		return int(stdin.readline())

	def In():
		return map(int, stdin.readline().split())

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 0
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def main():
	try:
		(n, q) = In()
		ans = 1
		l = list(In())
		for x in range(n - 1):
			if l[x] != l[x + 1]:
				ans += 1
		for i in range(q):
			(a, b) = In()
			a -= 1
			if l[a] == b:
				print(ans)
			else:
				if a - 1 >= 0 and l[a] == l[a - 1]:
					ans += 1
				if a + 1 < n and l[a + 1] == l[a]:
					ans += 1
				l[a] = b
				if a - 1 >= 0 and l[a - 1] == l[a]:
					ans -= 1
				if a + 1 < n and l[a + 1] == l[a]:
					ans -= 1
				print(ans)
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(I()):
	main()


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	if n == 1:
		input()
		for _ in range(q):
			input()
			print(1)
		continue
	elif n == 2:
		a = list(map(int, input().split()))
		for _ in range(q):
			(x, y) = map(int, input().split())
			a[x - 1] = y
			print(len(set(a)))
		continue
	a = list(map(int, input().split()))
	seq = 1
	for i in range(1, n):
		if a[i - 1] != a[i]:
			seq += 1
	for _ in range(q):
		prev_contr = 0
		contr = 0
		(x, y) = map(int, input().split())
		if a[x - 1] == y:
			print(seq)
			continue
		if x > 1 and a[x - 2] != a[x - 1]:
			prev_contr += 1
		if x < n and a[x] != a[x - 1]:
			prev_contr += 1
		a[x - 1] = y
		if x > 1 and a[x - 2] != a[x - 1]:
			contr += 1
		if x < n and a[x] != a[x - 1]:
			contr += 1
		seq += contr - prev_contr
		print(seq)


t = int(input())
while t > 0:
	(n, q) = map(int, input().split())
	seq = list(map(int, input().split()))
	length = 1
	for i in range(1, len(seq)):
		if seq[i] != seq[i - 1]:
			length += 1
	for i in range(q):
		(x, y) = map(int, input().split())
		x = x - 1
		if x != 0:
			if seq[x] != seq[x - 1]:
				length -= 1
			if y != seq[x - 1]:
				length += 1
		if x != len(seq) - 1:
			if seq[x] != seq[x + 1]:
				length -= 1
			if y != seq[x + 1]:
				length += 1
		seq[x] = y
		print(length)
	t -= 1


def solve():
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	length = 1
	for i in range(1, n):
		length += l[i] != l[i - 1]
	for i in range(q):
		(x, y) = map(int, input().split())
		x -= 1
		if x != 0:
			length -= l[x] != l[x - 1]
			length += y != l[x - 1]
		if x != n - 1:
			length -= l[x] != l[x + 1]
			length += y != l[x + 1]
		l[x] = y
		print(length)
t = int(input())
for _ in range(t):
	solve()


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	count = 0
	d = 'h'
	for i in range(n):
		if a[i] != d:
			count += 1
			d = a[i]
	for i in range(q):
		(x, y) = map(int, input().split())
		if n == 1 or y == a[x - 1]:
			a[x - 1] = y
			print(count)
		elif x == n:
			if a[x - 1] == a[x - 2]:
				a[x - 1] = y
				count += 1
			elif y == a[x - 2]:
				count -= 1
				a[x - 1] = y
			else:
				a[x - 1] = y
			print(count)
		elif x == 1:
			if a[x - 1] == a[x]:
				a[x - 1] = y
				count += 1
			elif a[x] == y:
				count -= 1
				a[x - 1] = y
			else:
				a[x - 1] = y
			print(count)
		elif a[x - 1] == a[x - 2] and a[x - 1] == a[x]:
			a[x - 1] = y
			count += 2
			print(count)
		elif a[x - 1] == a[x - 2] or a[x - 1] == a[x]:
			if a[x] == y or a[x - 2] == y:
				a[x - 1] = y
			else:
				a[x - 1] = y
				count += 1
			print(count)
		else:
			if y == a[x - 2]:
				count -= 1
			if y == a[x]:
				count -= 1
			a[x - 1] = y
			print(count)


import sys
from collections import defaultdict as df

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

def inp():
	return map(int, sys.stdin.readline().strip().split())

def li():
	return list(map(int, sys.stdin.readline().strip().split()))
for _ in range(ini()):
	(n, q) = inp()
	l = li()
	count = 1
	for i in range(1, n):
		count += 1 if l[i - 1] != l[i] else 0
	for __ in range(q):
		(a, b) = inp()
		i = a - 1
		if i > 0:
			count -= 1 if l[i - 1] != l[i] else 0
			count += 1 if l[i - 1] != b else 0
		if i < n - 1:
			count -= 1 if l[i + 1] != l[i] else 0
			count += 1 if l[i + 1] != b else 0
		l[i] = b
		print(count)


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))
for t in range(int(input())):
	(n, q) = get_ints()
	arr = get_array()
	count = 1
	for i in range(1, n):
		count += arr[i] != arr[i - 1]
	for j in range(q):
		(x, y) = get_ints()
		index = x - 1
		if index != 0:
			count -= arr[index] != arr[index - 1]
			count += y != arr[index - 1]
		if index != n - 1:
			count -= arr[index] != arr[index + 1]
			count += y != arr[index + 1]
		arr[index] = y
		print(count)


def getContributions(x, y, z):
	ans = 0
	if x != -1:
		ans += y != x
	if z != -1:
		ans += z != y
	return ans
t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 1
	for i in range(1, n):
		ans += arr[i] != arr[i - 1]
	for i in range(q):
		(x, y) = map(int, input().split())
		x -= 1
		if x != 0:
			ans -= arr[x] != arr[x - 1]
			ans += y != arr[x - 1]
		if x != n - 1:
			ans -= arr[x] != arr[x + 1]
			ans += y != arr[x + 1]
		arr[x] = y
		print(ans)


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	ls = list(map(int, input().split()))
	count = 1
	for i in range(1, n):
		if ls[i] != ls[i - 1]:
			count += 1
	for _ in range(q):
		(x, y) = map(int, input().split())
		x -= 1
		xc = 0
		if x != 0 and ls[x] != ls[x - 1]:
			xc += 1
		if x != n - 1 and ls[x] != ls[x + 1]:
			xc += 1
		yc = 0
		if x != 0 and y != ls[x - 1]:
			yc += 1
		if x != n - 1 and y != ls[x + 1]:
			yc += 1
		ls[x] = y
		count = count - xc + yc
		print(count)


T = int(input())
for _ in range(T):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	count = 1
	for i in range(1, a):
		if l[i - 1] != l[i]:
			count = count + 1
	for j in range(b):
		(c, d) = map(int, input().split())
		if c > 1:
			if l[c - 2] != l[c - 1]:
				count = count - 1
		if c < a:
			if l[c] != l[c - 1]:
				count = count - 1
		l[c - 1] = d
		if c > 1:
			if l[c - 2] != l[c - 1]:
				count = count + 1
		if c < a:
			if l[c] != l[c - 1]:
				count = count + 1
		print(count)


t = int(input())
while t != 0:
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	ln = 1
	for i in range(1, n):
		if arr[i] != arr[i - 1]:
			ln += 1
	for i in range(q):
		(x, y) = map(int, input().split())
		x -= 1
		pc = 0
		if x > 0 and arr[x] != arr[x - 1]:
			pc += 1
		if x < n - 1 and arr[x] != arr[x + 1]:
			pc += 1
		nc = 0
		if x > 0 and y != arr[x - 1]:
			nc += 1
		if x < n - 1 and y != arr[x + 1]:
			nc += 1
		ln = ln - pc + nc
		print(ln)
		arr[x] = y
	t -= 1


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 1
	for i in range(1, n):
		if arr[i - 1] != arr[i]:
			ans += 1
	for x in range(q):
		(ind, ele) = map(int, input().split())
		if ele == arr[ind - 1]:
			print(ans)
			continue
		if ind - 2 >= 0 and arr[ind - 1] == arr[ind - 2]:
			ans += 1
		if ind < n and arr[ind - 1] == arr[ind]:
			ans += 1
		arr[ind - 1] = ele
		if ind - 2 >= 0 and arr[ind - 1] == arr[ind - 2]:
			ans -= 1
		if ind < n and arr[ind - 1] == arr[ind]:
			ans -= 1
		print(ans)


for _ in range(int(input())):
	(n, q) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	ans = 1
	for i in range(1, n):
		if a[i] != a[i - 1]:
			ans += 1
	for i in range(q):
		(x, y) = map(int, input().strip().split())
		j = k = 0
		if x >= 2:
			if a[x - 1] != a[x - 2]:
				j += 1
			if y != a[x - 2]:
				k += 1
		if x < n:
			if a[x - 1] != a[x]:
				j += 1
			if y != a[x]:
				k += 1
		ans += k - j
		a[x - 1] = y
		print(ans)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	inp = list(map(int, input().split()))
	segment = 1
	ini = inp[0]
	for i in inp:
		if i != ini:
			segment += 1
			ini = i
	for _ in range(q):
		(x, y) = map(int, input().split())
		curr = inp[x - 1]
		inp[x - 1] = y
		if curr != y:
			if x == 1:
				if n != 1:
					if curr == inp[x]:
						segment += 1
					elif y == inp[x]:
						segment -= 1
			elif x == n:
				if n != 1:
					if curr == inp[x - 2]:
						segment += 1
					elif y == inp[x - 2]:
						segment -= 1
			elif inp[x - 2] == curr and inp[x] == curr:
				segment += 2
			elif inp[x - 2] == curr and y != inp[x]:
				segment += 1
			elif inp[x] == curr and y != inp[x - 2]:
				segment += 1
			elif inp[x - 2] != curr and curr != inp[x]:
				if inp[x - 2] == inp[x] == y:
					segment -= 2
				elif y == inp[x - 2] or y == inp[x]:
					segment -= 1
		print(segment)


for _ in range(int(input())):
	a = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	l = 1
	for i in range(a[0] - 1):
		if arr[i + 1] != arr[i]:
			l += 1
	if len(arr) == 1:
		print(1)
	else:
		for k in range(a[1]):
			b = list(map(int, input().split()))
			if b[0] == 1:
				if arr[1] != arr[0]:
					l -= 1
				if b[1] != arr[1]:
					l += 1
				arr[0] = b[1]
			elif b[0] == a[0]:
				if arr[a[0] - 1] != arr[a[0] - 2]:
					l -= 1
				if b[1] != arr[a[0] - 2]:
					l += 1
				arr[a[0] - 1] = b[1]
			else:
				if arr[b[0] - 1] == arr[b[0]] or arr[b[0] - 1] == arr[b[0] - 2]:
					if arr[b[0] - 1] == arr[b[0]] and arr[b[0] - 1] == arr[b[0] - 2]:
						l += 1
				else:
					l -= 1
				if b[1] == arr[b[0]] or b[1] == arr[b[0] - 2]:
					if b[1] == arr[b[0]] and b[1] == arr[b[0] - 2]:
						l -= 1
				else:
					l += 1
				arr[b[0] - 1] = b[1]
			print(l)


t = int(input())
for _ in range(t):
	(N, Q) = map(int, input().split())
	arr = list(map(int, input().split()))
	count = 1
	for i in range(N - 1):
		count += arr[i] != arr[i + 1]
	for q in range(Q):
		(x, y) = map(int, input().split())
		x -= 1
		if x != 0:
			count -= arr[x] != arr[x - 1]
			count += y != arr[x - 1]
		if x != N - 1:
			count -= arr[x] != arr[x + 1]
			count += y != arr[x + 1]
		arr[x] = y
		print(count)


for _ in range(int(input())):
	(n, q) = tuple(map(int, input().split()))
	arr = list(map(int, input().split()))
	result = 1
	for i in range(1, n):
		result += arr[i] != arr[i - 1]
	for i in range(q):
		(x, y) = tuple(map(int, input().split()))
		x -= 1
		if x != 0:
			if arr[x] == arr[x - 1]:
				result += 1
			if y == arr[x - 1]:
				result -= 1
		if x != n - 1:
			if arr[x] == arr[x + 1]:
				result += 1
			if y == arr[x + 1]:
				result -= 1
		arr[x] = y
		print(result)


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))
for _ in range(int(input())):
	(n, q) = get_ints()
	arr = get_list()
	ans = 1
	for i in range(1, n):
		ans += arr[i] != arr[i - 1]
	for i in range(q):
		(ind, y) = get_ints()
		x = ind - 1
		if x != 0:
			ans -= arr[x] != arr[x - 1]
			ans += y != arr[x - 1]
		if x != n - 1:
			ans -= arr[x] != arr[x + 1]
			ans += y != arr[x + 1]
		arr[x] = y
		print(ans)


for _ in range(int(input())):
	(n, q) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	ans = 1
	for i in range(1, n):
		ans += arr[i] != arr[i - 1]
	for i in range(q):
		(ind, y) = map(int, input().strip().split())
		x = ind - 1
		if x != 0:
			if arr[x] != arr[x - 1]:
				ans -= 1
			if y != arr[x - 1]:
				ans += 1
		if x != n - 1:
			if arr[x] != arr[x + 1]:
				ans -= 1
			if y != arr[x + 1]:
				ans += 1
		arr[x] = y
		print(ans)


for _ in range(int(input())):
	(n, q) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	count = 0
	count_lis = []
	for x in range(1, n):
		if arr[x - 1] == arr[x]:
			count += 1
		else:
			if count > 0:
				count_lis.append(count)
			count = 0
	if count > 0:
		count_lis.append(count)
	s = sum(count_lis)
	ans = n - s
	for i in range(q):
		(ind, y) = map(int, input().strip().split())
		x = ind - 1
		if x != 0:
			if arr[x] != arr[x - 1]:
				ans -= 1
			if y != arr[x - 1]:
				ans += 1
		if x != n - 1:
			if arr[x] != arr[x + 1]:
				ans -= 1
			if y != arr[x + 1]:
				ans += 1
		arr[x] = y
		print(ans)


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = n
	for i in range(n - 1):
		if l[i] == l[i + 1]:
			ans -= 1
	for P in range(q):
		(x, y) = map(int, input().split())
		x -= 1
		if l[x] == y:
			print(ans)
			continue
		if x != n - 1 and l[x] == l[x + 1]:
			ans += 1
		if x != 0 and l[x] == l[x - 1]:
			ans += 1
		if x != n - 1 and l[x + 1] == y:
			ans -= 1
		if x != 0 and l[x - 1] == y:
			ans -= 1
		print(ans)
		l[x] = y


try:
	t = int(input())
	for _ in range(t):
		(n, q) = map(int, input().split())
		l = list(map(int, input().split()))
		count = 1
		for i in range(n - 1, 0, -1):
			if l[i] != l[i - 1]:
				count += 1
		for i in range(q):
			(x, y) = map(int, input().split())
			a = 0
			if x < n:
				if l[x - 1] == l[x]:
					a += 1
			if x > 1:
				if l[x - 1] == l[x - 2]:
					a += 1
			l[x - 1] = y
			b = 0
			if x < n:
				if l[x - 1] == l[x]:
					b += 1
			if x > 1:
				if l[x - 1] == l[x - 2]:
					b += 1
			count = count + a - b
			print(count)
except:
	pass


for tc in range(int(input())):
	(n, q) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	l = 1
	for i in range(1, n):
		l += a[i] != a[i - 1]
	for i in range(q):
		(x, y) = map(int, input().strip().split())
		x -= 1
		if x != 0:
			l -= a[x] != a[x - 1]
			l += y != a[x - 1]
		if x != n - 1:
			l -= a[x] != a[x + 1]
			l += y != a[x + 1]
		a[x] = y
		print(l)


t = int(input())
for _ in range(t):
	(n, q) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	ans = 1
	for i in range(1, n):
		if a[i] != a[i - 1]:
			ans = ans + 1
	if n == 1:
		for i in range(q):
			print(1)
	else:
		for z in range(q):
			(x, y) = list(map(int, input().split()))
			x = x - 1
			if y != a[x]:
				if x > 0 and x < n - 1:
					if a[x] == a[x - 1] and a[x] == a[x + 1]:
						ans = ans + 2
					elif a[x] == a[x + 1] and a[x] != a[x - 1] and (y != a[x - 1]):
						ans = ans + 1
					elif a[x] == a[x - 1] and a[x] != a[x + 1] and (y != a[x + 1]):
						ans = ans + 1
					elif a[x] != a[x - 1] and a[x] != a[x + 1]:
						if y == a[x - 1]:
							ans = ans - 1
						if y == a[x + 1]:
							ans = ans - 1
				elif x == 0:
					if a[x] == a[x + 1]:
						ans = ans + 1
					elif y == a[x + 1]:
						ans = ans - 1
				elif x == n - 1:
					if a[x] == a[x - 1]:
						ans = ans + 1
					elif y == a[x - 1]:
						ans = ans - 1
			a[x] = y
			print(ans)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 1
	curr = a[0]
	for j in range(1, n):
		if a[j] != curr:
			c += 1
			curr = a[j]
	for i in range(q):
		(x, y) = map(int, input().split())
		p = 0
		if x < n:
			if a[x - 1] != a[x]:
				p -= 1
		if x > 1:
			if a[x - 1] != a[x - 2]:
				p -= 1
		a[x - 1] = y
		if x < n:
			if a[x - 1] != a[x]:
				p += 1
		if x > 1:
			if a[x - 1] != a[x - 2]:
				p += 1
		c += p
		print(c)


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	count = 1
	for j in range(1, len(arr)):
		if arr[j] != arr[j - 1]:
			count += 1
	for i in range(q):
		(x, y) = map(int, input().split())
		x = x - 1
		if x == 0 or arr[x] != arr[x - 1]:
			count -= 1
		if x + 1 < n and arr[x] != arr[x + 1]:
			count -= 1
		arr[x] = y
		if x == 0 or arr[x] != arr[x - 1]:
			count += 1
		if x + 1 < n and arr[x] != arr[x + 1]:
			count += 1
		print(count)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	lst = list(map(int, input().split()))
	(add, sub, ctr) = (0, 0, 1)
	for i in range(n - 1):
		if lst[i] != lst[i + 1]:
			ctr += 1
	for j in range(q):
		(x, y) = map(int, input().split())
		if x < n and lst[x - 1] == lst[x]:
			add += 1
		if x > 1 and lst[x - 1] == lst[x - 2]:
			add += 1
		lst[x - 1] = y
		if x < n:
			if lst[x - 1] == lst[x]:
				sub += 1
		if x > 1:
			if lst[x - 1] == lst[x - 2]:
				sub += 1
		print(ctr + add - sub)


t = int(input())
while t != 0:
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))[:n]
	c = 1
	if n == 1:
		print(1)
		t -= 1
		continue
	for i in range(1, n):
		if a[i] != a[i - 1]:
			c += 1
	for _ in range(q):
		(x, y) = map(int, input().split())
		k = x - 1
		(c_cont, p_cont) = (0, 0)
		if k == 0:
			if a[k] != a[k + 1]:
				p_cont += 1
		elif k == n - 1:
			if a[k] != a[k - 1]:
				p_cont += 1
		else:
			if a[k] != a[k + 1]:
				p_cont += 1
			if a[k] != a[k - 1]:
				p_cont += 1
		a[k] = y
		if k == 0:
			if a[k] != a[k + 1]:
				c_cont += 1
		elif k == n - 1:
			if a[k] != a[k - 1]:
				c_cont += 1
		else:
			if a[k] != a[k + 1]:
				c_cont += 1
			if a[k] != a[k - 1]:
				c_cont += 1
		c = c - p_cont + c_cont
		print(c)
	t -= 1


import sys
from collections import deque, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def solve():
	for _ in range(ii()):
		(n, q) = mi()
		a = li()
		ans = 1
		for i in range(1, n):
			if a[i] != a[i - 1]:
				ans += 1
		for i in range(q):
			(pos, val) = mi()
			pos -= 1
			prev = a[pos]
			a[pos] = val
			if pos < n - 1 and prev != a[pos + 1]:
				ans -= 1
			if pos < n - 1 and a[pos] != a[pos + 1]:
				ans += 1
			if pos > 0 and prev != a[pos - 1]:
				ans -= 1
			if pos > 0 and val != a[pos - 1]:
				ans += 1
			print(ans)
solve()


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 1
	for i in range(1, n):
		if a[i] != a[i - 1]:
			c += 1
	for j in range(q):
		(x, y) = map(int, input().split())
		x -= 1
		if x != 0:
			c -= a[x] != a[x - 1]
			c += y != a[x - 1]
		if x != n - 1:
			c -= a[x] != a[x + 1]
			c += y != a[x + 1]
		a[x] = y
		print(c)


t = int(input())
for i in range(t):
	(n, Q) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	count = 1
	for i in range(1, n):
		count += a[i] != a[i - 1]
	for i in range(Q):
		(x, y) = map(int, input().split())
		x = x - 1
		if x != 0:
			count -= a[x] != a[x - 1]
			count += y != a[x - 1]
		if x != n - 1:
			count -= a[x] != a[x + 1]
			count += y != a[x + 1]
		a[x] = y
		print(count)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	len = 1
	l = list(map(int, input().split(' ')))[:n]
	for i in range(1, n):
		len += l[i] != l[i - 1]
	for i in range(q):
		(x, y) = map(int, input().split())
		x = x - 1
		if x != 0:
			len -= l[x] != l[x - 1]
			len += y != l[x - 1]
		if x != n - 1:
			len -= l[x] != l[x + 1]
			len += y != l[x + 1]
		l[x] = y
		print(len)
	l.clear()


t = int(input())
while t > 0:
	t -= 1
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	query = [list(map(int, input().split())) for i in range(q)]
	maxi = 1
	for i in range(1, n):
		if l[i] != l[i - 1]:
			maxi += 1
	ans = maxi
	for i in query:
		i[0] -= 1
		prev = l[i[0]]
		l[i[0]] = i[1]
		if i[0] == 0:
			if i[0] + 1 <= n - 1:
				if l[0] == l[1]:
					if prev != l[0]:
						maxi -= 1
				elif prev == l[1]:
					maxi += 1
		elif i[0] == n - 1:
			if i[0] - 1 >= 0:
				if l[n - 1] == l[n - 2]:
					if prev != l[n - 1]:
						maxi -= 1
				elif prev == l[n - 2]:
					maxi += 1
		else:
			ind = i[0]
			if prev != l[ind]:
				if l[ind] == l[ind - 1] and l[ind] == l[ind + 1]:
					maxi -= 2
				elif l[ind] == l[ind - 1] or l[ind] == l[ind + 1]:
					maxi -= 1
				if prev == l[ind - 1]:
					maxi += 1
				if prev == l[ind + 1]:
					maxi += 1
		print(maxi)


for _ in range(int(input())):
	(n, y) = map(int, input().split())
	a = list(map(int, input().split()))
	l = 1
	for i in range(n - 1):
		if a[i] != a[i + 1]:
			l += 1
	for j in range(y):
		(p, q) = map(int, input().split())
		s = 0
		r = 0
		if p != 1 and a[p - 2] != a[p - 1]:
			s += 1
		if p != n and a[p - 1] != a[p]:
			s += 1
		a[p - 1] = q
		if p != 1 and a[p - 2] != a[p - 1]:
			r += 1
		if p != n and a[p - 1] != a[p]:
			r += 1
		if s > r:
			l = l - abs(s - r)
		elif r > s:
			l = l + abs(s - r)
		print(l)


l1 = int(input())
for _ in range(l1):
	(n, q) = map(int, input().split())
	s = list(map(int, input().split()))
	count = 1
	pre = s[0]
	for j in s[1:]:
		if j != pre:
			count += 1
			pre = j
	for i in range(q):
		(x, y) = map(int, input().split())
		x -= 1
		if x - 1 >= 0:
			if s[x - 1] != s[x]:
				count -= 1
			if s[x - 1] != y:
				count += 1
		if x + 1 < n:
			if s[x] != s[x + 1]:
				count -= 1
			if s[x + 1] != y:
				count += 1
		print(count)
		s[x] = y


for testis in range(int(input())):
	(n, q) = map(int, input().split())
	p = list(map(int, input().split()))
	l = p.copy()
	a = 1
	for i in range(1, n):
		if l[i] != l[i - 1]:
			a = a + 1
	for ii in range(q):
		(x, y) = map(int, input().split())
		x = x - 1
		if x != 0:
			a = a - (l[x] != l[x - 1])
			a = a + (l[x - 1] != y)
		if x != n - 1:
			a = a - (l[x] != l[x + 1])
			a = a + (l[x + 1] != y)
		l[x] = y
		print(a)


input = __import__('sys').stdin.readline
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 1
	for i in range(1, n):
		if a[i] != a[i - 1]:
			ans += 1
	for i in range(q):
		if n == 1:
			print(1)
			continue
		(x, y) = map(int, input().split())
		x -= 1
		if x == 0:
			old = 0
			new = 0
			if a[x] != a[x + 1]:
				old += 1
			if y != a[x + 1]:
				new += 1
			ans = ans - old + new
			a[x] = y
		elif x == n - 1:
			old = 0
			new = 0
			if a[x] != a[x - 1]:
				old += 1
			if y != a[x - 1]:
				new += 1
			ans = ans - old + new
			a[x] = y
		else:
			old = 0
			new = 0
			if a[x] != a[x - 1]:
				old += 1
			if a[x + 1] != a[x]:
				old += 1
			if y != a[x - 1]:
				new += 1
			if a[x + 1] != y:
				new += 1
			a[x] = y
			ans = ans - old + new
		print(ans)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 1
	for i in range(1, n):
		if l[i] != l[i - 1]:
			c += 1
	for i in range(q):
		(x, y) = map(int, input().split())
		x = x - 1
		if x - 1 >= 0:
			if l[x - 1] == l[x] and l[x - 1] != y:
				c += 1
			elif l[x - 1] != l[x] and l[x - 1] == y:
				c -= 1
		if x + 1 < n:
			if l[x + 1] == l[x] and l[x + 1] != y:
				c += 1
			elif l[x + 1] != l[x] and l[x + 1] == y:
				c -= 1
		l[x] = y
		print(c)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	length = 1
	for i in range(1, len(arr)):
		if arr[i - 1] != arr[i]:
			length += 1
	for i in range(q):
		(x, y) = map(int, input().split())
		x = x - 1
		if x != 0:
			length -= arr[x] != arr[x - 1]
			length += y != arr[x - 1]
		if x != n - 1:
			length -= arr[x] != arr[x + 1]
			length += y != arr[x + 1]
		arr[x] = y
		print(length)