This is the hard version of the problem. The only difference between the two versions is that the harder version asks additionally for a minimum number of subsegments.

Tokitsukaze has a binary string $s$ of length $n$, consisting only of zeros and ones, $n$ is even.

Now Tokitsukaze divides $s$ into the minimum number of contiguous subsegments, and for each subsegment, all bits in each subsegment are the same. After that, $s$ is considered good if the lengths of all subsegments are even.

For example, if $s$ is "11001111", it will be divided into "11", "00" and "1111". Their lengths are $2$, $2$, $4$ respectively, which are all even numbers, so "11001111" is good. Another example, if $s$ is "1110011000", it will be divided into "111", "00", "11" and "000", and their lengths are $3$, $2$, $2$, $3$. Obviously, "1110011000" is not good.

Tokitsukaze wants to make $s$ good by changing the values of some positions in $s$. Specifically, she can perform the operation any number of times: change the value of $s_i$ to '0' or '1' ($1 \leq i \leq n$). Can you tell her the minimum number of operations to make $s$ good? Meanwhile, she also wants to know the minimum number of subsegments that $s$ can be divided into among all solutions with the minimum number of operations.


-----Input-----

The first contains a single positive integer $t$ ($1 \leq t \leq 10000$) — the number of test cases.

For each test case, the first line contains a single integer $n$ ($2 \leq n \leq 2 \cdot 10^5$) — the length of $s$, it is guaranteed that $n$ is even.

The second line contains a binary string $s$ of length $n$, consisting only of zeros and ones.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print a single line with two integers — the minimum number of operations to make $s$ good, and the minimum number of subsegments that $s$ can be divided into among all solutions with the minimum number of operations.


-----Examples-----

Input
5
10
1110011000
8
11001111
2
00
2
11
6
100110
Output
3 2
0 3
0 1
0 1
3 1


-----Note-----

In the first test case, one of the ways to make $s$ good is the following.

Change $s_3$, $s_6$ and $s_7$ to '0', after that $s$ becomes "1100000000", it can be divided into "11" and "00000000", which lengths are $2$ and $8$ respectively, the number of subsegments of it is $2$. There are other ways to operate $3$ times to make $s$ good, such as "1111110000", "1100001100", "1111001100", the number of subsegments of them are $2$, $4$, $4$ respectively. It's easy to find that the minimum number of subsegments among all solutions with the minimum number of operations is $2$.

In the second, third and fourth test cases, $s$ is good initially, so no operation is required.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Implementation

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	s = input()
	ans1 = 0
	ans2 = 0
	ans = ''
	last = '!'
	for i in range(0, n, 2):
		if s[i] != s[i + 1]:
			ans1 += 1
		elif s[i] != last:
			ans2 += 1
			last = s[i]
	if ans2 == 0:
		ans2 += 1
	print(ans1, ans2)
	return
for _ in range(int(input())):
	solve()


from typing import Tuple

def solve() -> Tuple[int, int]:
	n = int(input())
	string = input()
	last = -1
	x = y = 0
	for index in range(0, n, 2):
		if string[index] != string[index + 1]:
			x += 1
		else:
			if last != string[index]:
				y += 1
			last = string[index]
	return (x, max(y, 1))
results = []
for _ in range(int(input())):
	(x, y) = solve()
	results.append(f'{x} {y}')
print('\n'.join(results))


import sys
input = sys.stdin.readline
from array import array

def solve():
	n = int(input())
	s = list(input().rstrip())
	count = 0
	minSegs = 0
	LAST = -1
	for i in range(0, len(s), 2):
		if s[i] != s[i + 1]:
			count += 1
		else:
			minSegs += s[i] != LAST
			LAST = s[i]
	return (count, max(minSegs, 1))
for _ in range(int(input())):
	print(*solve())


import sys

def input():
	return sys.stdin.readline().rstrip()

def main():
	t = int(input())
	for tc in range(t):
		n = int(input())
		string = input()
		opr_cnt = 0
		sub_cnt = 0
		cur_num = 'NULL'
		for i in range(0, n, 2):
			if string[i] == string[i + 1]:
				if string[i] != cur_num:
					sub_cnt += 1
					cur_num = string[i]
			else:
				opr_cnt += 1
		sub_cnt = 1 if sub_cnt == 0 else sub_cnt
		print(opr_cnt, sub_cnt)
main()


t = int(input())
out = ''
for _ in range(t):
	n = int(input())
	string = input()
	ans = 0
	ans2 = 1
	last = ''
	for i in range(0, len(string), 2):
		if string[i] != string[i + 1]:
			ans += 1
		else:
			if last != '' and string[i] != last:
				ans2 += 1
			last = string[i]
	out += str(ans) + ' ' + str(ans2) + '\n'
print(out)


import sys
import math
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()
	res1 = 0
	ans = 1
	first = True
	for i in range(0, n - 1, 2):
		if s[i] != s[i + 1]:
			res1 += 1
		elif first:
			cur = s[i]
			first = False
		elif s[i] != cur:
			ans += 1
			cur = s[i]
	print(res1, ans)


import sys
input = sys.stdin.readline
from array import array

def solve():
	n = int(input())
	s = array('u', input().rstrip())
	count = 0
	minimalSegments = 0
	L = '3'
	for i in range(0, len(s), 2):
		if s[i] != s[i + 1]:
			count += 1
		else:
			if L != s[i]:
				minimalSegments += 1
			L = s[i]
	return (count, max(1, minimalSegments))
for _ in range(int(input())):
	ret = solve()
	print(ret[0], ret[1])


for i in range(int(input())):
	n = int(input())
	s = input()
	counter_change = 0
	counter_segment = 0
	p = 'p'
	for k in range(0, n, 2):
		if s[k] != s[k + 1]:
			counter_change += 1
		else:
			if p != s[k]:
				counter_segment += 1
			p = s[k]
	if counter_segment == 0:
		counter_segment = 1
	print(counter_change, counter_segment)


t1 = int(input())
for hi in range(t1):
	n = int(input())
	s = str(input())
	p = 0
	o = True
	l = 1
	for i in range(0, n, 2):
		if s[i] != s[i + 1]:
			p += 1
		elif o:
			c = s[i]
			o = False
		elif c != s[i]:
			l += 1
			c = s[i]
	print(p, l)


t = int(input())
for tt in range(t):
	n = int(input())
	s = input()
	count_o = 0
	count_s = 0
	cur = -1
	for i in range(0, n - 1, 2):
		if s[i] != s[i + 1]:
			count_o += 1
		elif s[i] != cur:
			count_s += 1
			cur = s[i]
	if cur == -1:
		count_s = 1
	print(count_o, count_s)


t = int(input())
for vvod in range(t):
	n = int(input())
	str = input()
	s = list(str)
	ans = 0
	pok = 0
	if n == 2:
		if s[0] == s[1]:
			print('0 1')
		else:
			print('1 1')
		continue
	d = dict()
	c = 'p'
	ans2 = 0
	for i in range(0, n - 1, 2):
		if s[i] == s[i + 1]:
			if c != s[i]:
				ans2 += 1
				c = s[i]
		else:
			ans += 1
	if c == 'p':
		ans2 = 1
	print(ans, ans2)


for zzzzz in range(int(input())):
	n = int(input())
	a = input()
	count = 0
	isprev = '-1'
	count2 = 0
	for i in range(0, n, 2):
		f = a[i]
		s = a[i + 1]
		if f != s:
			count = count + 1
		if f == s:
			if isprev == '-1':
				if f == '0':
					isprev = '0'
				else:
					isprev = '1'
				count2 = count2 + 1
			elif isprev != f:
				count2 = count2 + 1
				isprev = f
	if count2 == 0:
		count2 = 1
	print(count, count2)


n = int(input())
while n:
	n -= 1
	dlch = int(input())
	ch = input()
	count = 0
	s = ''
	otv = 1
	for i in range(1, dlch, 2):
		if ch[i] != ch[i - 1]:
			count += 1
		elif ch[i] == '1' and ch[i - 1] == '1':
			s = s + '1'
		else:
			s = s + '0'
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			otv += 1
	print(count, otv)


T = int(input())
for _ in range(0, T):
	n = int(input())
	s = input()
	x1 = -1
	x = 0
	y = 0
	f = 0
	for i in range(0, n // 2):
		j1 = i * 2
		j2 = i * 2 + 1
		if s[j1] == s[j2] and x1 != int(s[j1]):
			y += 1
			x1 = int(s[j1])
		elif s[j1] != s[j2]:
			x += 1
			f = 1
	if y == 0:
		y = 1
	print(x, y, end='\n')


def solve():
	x = int(input())
	a = input()
	position = []
	count = 0
	counti = 0
	l = -1
	for i in range(0, x, 2):
		if a[i:i + 2] == '01' or a[i:i + 2] == '10':
			counti = counti + 1
		else:
			if l != a[i]:
				count = count + 1
			l = a[i]
	return (counti, max(count, 1))
tc = int(input())
for i in range(tc):
	x = solve()
	print(x[0], x[1])


for _ in range(int(input().strip())):
	n = int(input().strip())
	arr = input()
	ans = 0
	t = []
	for i in range(0, len(arr), 2):
		if arr[i] != arr[i + 1]:
			ans += 1
		else:
			t.append(arr[i])
	seg = 1
	for i in range(0, len(t) - 1):
		if t[i] != t[i + 1]:
			seg += 1
	print(ans, seg)


import collections
from math import ceil, gcd, sqrt, log
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	s = input()
	sub = 0
	opr = 0
	prev_bit = -1
	for i in range(0, n, 2):
		if s[i] == s[i + 1]:
			if s[i] != prev_bit:
				sub += 1
				prev_bit = s[i]
		else:
			opr += 1
	print(opr, max(1, sub))
t = int(input())
while t != 0:
	solve()
	t -= 1


from typing import List, Optional
import collections as co

def solver(pal):
	lista = [pal[x:x + 2] for x in range(0, len(pal), 2)]
	res = 0
	for x in lista:
		if x == '10' or x == '01':
			res += 1
	viejox = ''
	segmentos = 0
	for x in lista:
		if viejox == '':
			if x == '10' or x == '01':
				pass
			else:
				viejox = x
				segmentos = 1
		elif x == viejox:
			pass
		elif x == '10' or x == '01':
			pass
		elif viejox != x:
			viejox = x
			segmentos += 1
	return (res, max(1, segmentos))
for _ in range(int(input())):
	input()
	res = solver(input())
	print(res[0], res[1])


for _ in range(int(input())):
	n = int(input())
	s = input()
	i = 0
	count = 0
	while i < n - 1:
		if s[i] != s[i + 1]:
			count += 1
		i += 2
	i = 0
	prev = None
	count2 = 1
	while i < n - 1:
		if s[i] == s[i + 1]:
			if prev is not None:
				if prev != s[i]:
					count2 += 1
			prev = s[i]
		i += 2
	print(count, count2)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	count = 0
	first = True
	ans = 1
	for i in range(0, n, 2):
		if s[i] != s[i + 1]:
			count += 1
		elif first:
			cur = s[i]
			first = False
		elif s[i] != cur:
			ans += 1
			cur = s[i]
	print(count, ans)


for t in range(int(input())):
	n = int(input())
	a = [int(y) for y in input()]
	p = -1
	ans = 0
	seg = 0
	for i in range(0, n, 2):
		if a[i] ^ a[i + 1]:
			ans += 1
		else:
			seg += p != a[i]
			p = a[i]
	print(ans, max(1, seg))


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	count = 0
	count1 = 0
	flag = 0
	mark = '2'
	for k in range(n // 2):
		if a[2 * k] != a[2 * k + 1]:
			count += 1
		elif a[2 * k] != mark:
			mark = a[2 * k]
			count1 += 1
	if count1 == 0:
		count1 += 1
	print(count, count1)


[print(*__import__('functools').reduce(lambda x, y: [(x[0] + 1, x[1], x[2]), (x[0], x[1] + (x[2] and y[0] != x[2]), y[0])][y[0] == y[1]], zip(*[iter(input())] * 2), (0, 1, 0))[:-1]) for p in (input() for m in range(int(input())))]


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	(num, cnt) = (0, 0)
	tmp = -1
	for i in range(0, n, 2):
		if s[i] != s[i + 1]:
			num += 1
		elif s[i] != tmp:
			cnt += 1
			tmp = s[i]
	print(num, max(1, cnt))


t = int(input())
for i in range(0, t):
	count = 0
	n = int(input())
	s = input()
	j = 0
	f = 0
	k = 5
	for i in range(0, n, 2):
		if s[i] != s[i + 1]:
			count += 1
		elif f == 0:
			f = 1
			k = s[i]
		elif s[i] != k:
			j += 1
			k = s[i]
	print(count, end=' ')
	print(j + 1)


for ii in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	for i in range(0, n - 1, 2):
		if s[i] != s[i + 1]:
			ans += 1
	seg = 0
	last = 2
	for i in range(0, n - 1, 2):
		curr = 2
		if s[i] == s[i + 1] and s[i] == '0':
			curr = 0
		if s[i] == s[i + 1] and s[i] == '1':
			curr = 1
		if last == 0 and curr == 1:
			seg += 1
			last = 1
		if last == 1 and curr == 0:
			seg += 1
			last = 0
		if last == 2:
			last = curr
	print(ans, seg + 1)


t = int(input())
for _ in range(t):
	n = int(input())
	mas = list(input())
	new = []
	count = 0
	for i in range(1, n, 2):
		if mas[i] == mas[i - 1]:
			new.append(int(mas[i]))
		else:
			new.append(2)
			count += 1
	line = 1
	temp = 2
	for i in range(n // 2):
		if new[i] != 2:
			if temp == 2:
				temp = new[i]
			if temp != new[i]:
				temp = new[i]
				line += 1
	print(count, line)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	l = 0
	k = 0
	a = []
	for i in range(0, n, 2):
		if s[i] == s[i + 1]:
			a.append(int(s[i]))
		else:
			a.append(-1)
			l += 1
	x = []
	for i in range(len(a)):
		if a[i] == -1:
			continue
		elif a[i] == 0:
			if not x:
				x.append(a[i])
			elif x[-1] != a[i]:
				x.append(a[i])
				k += 3
		elif not x:
			x.append(a[i])
			k += 3
		elif x[-1] != a[i]:
			x.append(a[i])
			k += 3
	if x:
		k += 2
	if not x:
		x.append(1)
	print(l, len(x))


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(input())
	l = '1'
	ans = 0
	for i in range(0, n, 2):
		if s[i] == s[i + 1]:
			l = s[i + 1]
			break
	for i in range(0, len(s), 2):
		if s[i] == s[i + 1]:
			l = s[i + 1]
		else:
			ans += 1
			s[i] = l
			s[i + 1] = l
	ans1 = 0
	l = 'b'
	for i in range(n):
		if s[i] != l:
			ans1 += 1
			l = s[i]
	print(ans, ans1)


t = int(input())
for _ in range(t):
	n = int(input())
	st = input()
	arr = []
	count = 1
	for i in range(n - 1):
		if st[i] != st[i + 1]:
			arr.append(count)
			count = 1
		else:
			count += 1
	ans = 0
	for i in range(len(arr)):
		if arr[i] % 2 != 0:
			ans += 1
			if i + 1 < len(arr):
				arr[i + 1] -= 1
	ct_sb = 1
	prev = -1
	for i in range(0, n, 2):
		if st[i] == st[i + 1]:
			if prev == -1:
				prev = i
			elif st[prev] != st[i]:
				prev = i
				ct_sb += 1
	print(ans, ct_sb)


def solve(n, s):
	op = 0
	state = [(1, 1)]
	for i in range(0, len(s), 2):
		j = i + 1
		if s[i] == s[j]:
			v = int(s[i])
			x = min(state[-1][1 - v] + 1, state[-1][v])
			state.append((x, float('inf')) if v == 0 else (float('inf'), x))
		else:
			op += 1
			state.append((min(state[-1][0], state[-1][1] + 1), min(state[-1][0] + 1, state[-1][1])))
	print(f'{op} {min(state[-1][0], state[-1][1])}')
t = int(input())
10000
while t:
	n = int(input())
	s = input()
	solve(n, s)
	t -= 1


for _ in range(int(input())):
	(n, S) = (int(input()), input())
	(DP_, DP0, DP1, p0, p1) = ([0], [1], [1], '0', '1')
	for i in range(0, n, 2):
		DP_.append(0)
		DP0.append(0)
		DP1.append(0)
		if S[i] == S[i + 1]:
			DP0[-1] = DP0[-2] + (0 if p0 == S[i] else 1)
			DP1[-1] = DP1[-2] + (0 if p1 == S[i] else 1)
			(DP_[-1], p0, p1) = (DP_[-2], S[i], S[i])
		else:
			(DP_[-1], DP0[-1], DP1[-1]) = (1 + DP_[-2], DP0[-2], DP1[-2])
		pass
	print(DP_[-1], min(DP0[-1], DP1[-1]))
	pass


def isGood(s):
	if s[0] == s[1]:
		return 1
	return 0
for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	kekw = []
	kekw2 = []
	for i in range(0, n, 2):
		if s[i:i + 2] == '10' or s[i:i + 2] == '01':
			kekw.append(i)
			ans += 1
		else:
			kekw2.append(i)
	if len(kekw) == n // 2:
		print(ans, 1)
	else:
		temp = 1
		i = 0
		while i < len(kekw2) - 1:
			if s[kekw2[i]:kekw2[i] + 2] == s[kekw2[i + 1]:kekw2[i + 1] + 2]:
				pass
			else:
				temp += 1
			i += 1
		print(ans, temp)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	s = input().strip()
	ops = 0
	dp = [[float('inf'), float('inf')] for _ in range(n // 2)]
	if s[0] == s[1]:
		dp[0][int(s[1])] = 1
	else:
		dp[0][int(s[0])] = 1
		dp[0][int(s[1])] = 1
		ops += 1
	for i in range(1, n // 2):
		(c1, c2) = (s[i * 2], s[i * 2 + 1])
		if c1 == c2:
			dp[i][int(c2)] = min(dp[i - 1][0], dp[i - 1][1] + 1) if c2 == '0' else min(dp[i - 1][0] + 1, dp[i - 1][1])
		else:
			dp[i][0] = min(dp[i - 1][0], dp[i - 1][1] + 1)
			dp[i][1] = min(dp[i - 1][0] + 1, dp[i - 1][1])
			ops += 1
	return (ops, min(dp[-1]))
for _ in range(int(input())):
	print(*solve())


def countsegs(s):
	cnt = 1
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			cnt += 1
	return cnt
tc = int(input())
for case in range(tc):
	n = int(input())
	s = list(input())
	moves = 0
	for i in range(0, n, 2):
		if s[i] != s[i + 1]:
			moves += 1
	prevs = ['0', '1']
	mn = countsegs(s)
	for pre in prevs:
		x = s[:]
		for i in range(0, n, 2):
			if x[i] == x[i + 1]:
				pre = x[i]
			else:
				x[i] = pre
				x[i + 1] = pre
		mn = min(mn, countsegs(x))
	print(moves, mn)


for _ in range(int(input())):
	n = int(input())
	a = list(input())
	b = a[:]
	i = 0
	count = 0
	while i < n:
		if a[i:i + 2] == ['1', '1'] or a[i:i + 2] == ['0', '0']:
			i += 2
		else:
			count += 1
			i += 2
	if a[0] != a[1]:
		a[0] = '0'
		a[1] = '0'
		d = ['0', '0']
	else:
		d = a[:2]
	for i in range(2, n, 2):
		if a[i:i + 2] == ['1', '1'] or a[i:i + 2] == ['0', '0']:
			d = a[i:i + 2]
		else:
			a[i:i + 2] = d
	if b[0] != b[1]:
		b[0] = '1'
		b[1] = '1'
		d = ['1', '1']
	else:
		d = b[:2]
	for i in range(2, n, 2):
		if b[i:i + 2] == ['1', '1'] or b[i:i + 2] == ['0', '0']:
			d = b[i:i + 2]
		else:
			b[i:i + 2] = d
	count1 = 1
	count2 = 1
	c1 = a[0]
	c2 = b[0]
	for i in range(2, n, 2):
		if a[i] != c1:
			count1 += 1
			c1 = a[i]
		if b[i] != c2:
			count2 += 1
			c2 = b[i]
	print(count, min(count1, count2))