The only difference between the two versions is that this version asks the maximal possible answer.

Homer likes arrays a lot. Today he is painting an array $a_1, a_2, \dots, a_n$ with two kinds of colors, white and black. A painting assignment for $a_1, a_2, \dots, a_n$ is described by an array $b_1, b_2, \dots, b_n$ that $b_i$ indicates the color of $a_i$ ($0$ for white and $1$ for black).

According to a painting assignment $b_1, b_2, \dots, b_n$, the array $a$ is split into two new arrays $a^{(0)}$ and $a^{(1)}$, where $a^{(0)}$ is the sub-sequence of all white elements in $a$ and $a^{(1)}$ is the sub-sequence of all black elements in $a$. For example, if $a = [1,2,3,4,5,6]$ and $b = [0,1,0,1,0,0]$, then $a^{(0)} = [1,3,5,6]$ and $a^{(1)} = [2,4]$.

The number of segments in an array $c_1, c_2, \dots, c_k$, denoted $\mathit{seg}(c)$, is the number of elements if we merge all adjacent elements with the same value in $c$. For example, the number of segments in $[1,1,2,2,3,3,3,2]$ is $4$, because the array will become $[1,2,3,2]$ after merging adjacent elements with the same value. Especially, the number of segments in an empty array is $0$.

Homer wants to find a painting assignment $b$, according to which the number of segments in both $a^{(0)}$ and $a^{(1)}$, i.e. $\mathit{seg}(a^{(0)})+\mathit{seg}(a^{(1)})$, is as large as possible. Find this number.


-----Input-----

The first line contains an integer $n$ ($1 \leq n \leq 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq n$).


-----Output-----

Output a single integer, indicating the maximal possible total number of segments.


-----Examples-----

Input
7
1 1 2 2 3 3 3
Output
6
Input
7
1 2 3 4 5 6 7
Output
7


-----Note-----

In the first example, we can choose $a^{(0)} = [1,2,3,3]$, $a^{(1)} = [1,2,3]$ and $\mathit{seg}(a^{(0)}) = \mathit{seg}(a^{(1)}) = 3$. So the answer is $3+3 = 6$.

In the second example, we can choose $a^{(0)} = [1,2,3,4,5,6,7]$ and $a^{(1)}$ is empty. We can see that $\mathit{seg}(a^{(0)}) = 7$ and $\mathit{seg}(a^{(1)}) = 0$. So the answer is $7+0 = 7$.

Difficulty: HARD
Tags: Constructive algorithms

Implementation

Greedy algorithms

Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures

Greedy algorithms

Starter code:

Solutions:
import sys

def rl(proc=None):
	if proc is not None:
		return proc(sys.stdin.readline())
	else:
		return sys.stdin.readline().rstrip()

def srl(proc=None):
	if proc is not None:
		return list(map(proc, rl().split()))
	else:
		return rl().split()

def good(r, v):
	return any((r[i] != v for i in range(1, len(r), 2)))

def main():
	rl()
	A = srl(int)
	v = A[0]
	c = 0
	ret = 0
	r = []
	last_bulk = -1
	A.append(0)
	for x in A:
		if x == v:
			c += 1
		else:
			if c == 1:
				r.append(v)
			else:
				if v != last_bulk:
					ret += len(r) + 2
					last_bulk = v
				elif good(r, v):
					ret += len(r) + 2
				else:
					ret += len(r) + 1
				r = []
			v = x
			c = 1
	assert c == 1
	assert v == 0
	ret += len(r)
	print(ret)
main()


import sys
input = sys.stdin.readline
flush = sys.stdout.flush

def stupid(pos, p1, p2, c1, c2, a):
	if pos == len(a):
		return p1 + p2
	return max(stupid(pos + 1, a[pos], p2, c1 + int(p1 != a[pos]), c2, a), stupid(pos + 1, p1, a[pos], c1, c2 + int(p2 != a[pos]), a))

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	p = -1
	p1 = -1
	pos1 = -1
	c1 = 0
	c2 = 0
	j = 0
	for i in a:
		if i != p:
			p = i
			c1 += 1
		else:
			if i != p1:
				c2 += 1
			else:
				for k in range(pos1 + 1, j):
					if a[k] != p1 and a[k - 1] != a[k + 1]:
						c2 += 1
						break
			p1 = i
			pos1 = j
		j += 1
	print(c1 + c2)
solve()


def painting_the_array_i(array):
	count = 0
	last1 = None
	last2 = None
	buffer = None
	buffer_count = 0
	for i in array:
		if last1 is None or (i != last1 and last2 is None):
			last1 = i
			count += 1
		elif last2 is None:
			last2 = i
			count += 1
		elif last1 == last2:
			if i != last1:
				count += 1
			last1 = i
		elif i == last1 and buffer is None:
			last2 = i
			count += 1
		elif i == last2 and buffer is None:
			last1 = i
			count += 1
		elif i == buffer:
			last1 = last2 = i
			count += buffer_count
			count += 1
			buffer = None
			buffer_count = 0
		else:
			buffer = i
			buffer_count += 1
	return count + buffer_count
n = int(input())
array = [int(i) for i in input().split()]
print(painting_the_array_i(array))


import sys

def main():
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	last_pair = -1
	res = 0
	lhs = (0, a[0])
	for (key, value) in enumerate(a):
		if value != lhs[1]:
			if lhs[1] != last_pair and value != last_pair:
				last_pair = -1
			if key - lhs[0] > 1:
				res += 1
				if lhs[1] == last_pair:
					res -= 1
				last_pair = lhs[1]
			res += 1
			lhs = (key, value)
	res += 1
	if n - lhs[0] > 1:
		res += 1
		if lhs[1] == last_pair:
			res -= 1
	print(res)
	return
main()


from array import array

def solve(n, D):
	a = None
	b = None
	a_cnt = 0
	b_cnt = 0
	for (i, d) in enumerate(D):
		if a != d:
			if i < n - 1 and b == D[i + 1]:
				b_cnt += 1
				b = d
				continue
			a_cnt += 1
			a = d
			continue
		if b != d:
			b_cnt += 1
			b = d
	return a_cnt + b_cnt

def main():
	ans = []
	n = int(input())
	D = array('i', list(map(int, input().split(' '))))
	ans.append(solve(n, D))
	for a in ans:
		print(a)
main()


n = int(input())
a = list(map(int, input().split()))
(res, b, c) = (0, 0, 0)
for i in range(n):
	if a[i] != b and a[i] != c:
		if i + 1 < n and a[i + 1] == c:
			c = a[i]
		else:
			b = a[i]
		res += 1
	elif a[i] != b:
		b = a[i]
		res += 1
	elif a[i] != c:
		c = a[i]
		res += 1
print(res)


import sys
input = sys.stdin.readline
getint = lambda : int(input())
getints = lambda : [int(a) for a in input().split()]

def solve():
	n = getint()
	values = getints()
	pos = [-1 for i in range(n + 1)]
	next = [n for i in range(n)]
	for i in range(n):
		if pos[values[i]] != -1:
			next[pos[values[i]]] = i
		pos[values[i]] = i
	one = -1
	two = -1
	onei = -1
	twoi = -1
	segments = 0
	for i in range(n):
		v = values[i]
		if v == two:
			segments += 1 if v != one else 0
			one = v
			onei = i
		elif v == one:
			segments += 1
			two = v
			twoi = i
		elif next[onei] > next[twoi]:
			segments += 1
			two = v
			twoi = i
		else:
			segments += 1
			one = v
			onei = i
	print(segments)
solve()


import os
import sys
import string
import math

class Helper:

	def main(self):
		_ = self._readInt()
		case = self._readIntArray()
		result = self.solve(case)
		print(result)

	def _readString(self) -> str:
		return input()

	def _readInt(self):
		return int(self._readString())

	def _readIntArray(self):
		return [int(item) for item in self._readString().split(' ')]

	def readCase(self):
		raise NotImplementedError

	def solve(self, *args):
		raise NotImplementedError

	def postSolve(self, res):
		return res

class Solution(Helper):

	def readCase(self):
		pass

	def solve(self, nums):
		prev1 = None
		prev2 = None
		count = 0
		for (i, num) in enumerate(nums):
			if num == prev1 and num != prev2:
				prev2 = num
				count += 1
			elif num == prev2 and num != prev1:
				prev1 = num
				count += 1
			elif num == prev1 and num == prev2:
				continue
			else:
				later = None
				if i + 1 < len(nums):
					later = nums[i + 1]
				if later == prev1:
					prev1 = num
				elif later == prev2:
					prev2 = num
				else:
					prev1 = num
				count += 1
		return count
Solution().main()


n = int(input())
a = list(map(int, input().split()))
w = [0]
b = [0]
for i in range(n):
	if a[i] != w[-1] and a[i] != b[-1]:
		if i + 1 <= n - 1 and a[i + 1] == b[-1]:
			b.append(a[i])
		else:
			w.append(a[i])
	elif a[i] != w[-1]:
		w.append(a[i])
	elif a[i] != b[-1]:
		b.append(a[i])
print(len(w) + len(b) - 2)


n = int(input())
arr = [int(s) for s in input().split(' ')]
ans = 0
lastArray1 = 0
lastArray2 = 0
for i in range(n):
	if arr[i] != lastArray1 and arr[i] != lastArray2:
		if i + 1 < n and arr[i + 1] == lastArray2:
			lastArray2 = arr[i]
		else:
			lastArray1 = arr[i]
		ans += 1
	elif arr[i] != lastArray1:
		lastArray1 = arr[i]
		ans += 1
	elif arr[i] != lastArray2:
		lastArray2 = arr[i]
		ans += 1
print(ans)


import math
import sys
YES = 'YES'
NO = 'NO'
MOD = 1000000007

def input_int():
	return int(input())

def input_list():
	return input().split(' ')

def input_list_int():
	return list(map(int, input_list()))

def solve():
	n = input_int()
	a = [0] * (n + 1)
	a[1:] = input_list_int()
	pos = [n + 1] * (n + 1)
	nxt = [0] * (n + 1)
	for j in range(0, n + 1):
		i = n - j
		nxt[i] = pos[a[i]]
		pos[a[i]] = i
	x = 0
	y = 0
	sum = 0
	for i in range(1, n + 1):
		if a[x] == a[i]:
			sum += 1 if a[y] != a[i] else 0
			y = i
		elif a[y] == a[i]:
			sum += 1 if a[x] != a[i] else 0
			x = i
		elif nxt[x] < nxt[y]:
			sum += 1 if a[x] != a[i] else 0
			x = i
		else:
			sum += 1 if a[y] != a[i] else 0
			y = i
	print(sum)
query_count = 1
while query_count:
	query_count -= 1
	solve()


x = int(input())
l = [int(i) for i in input().split()]
(c, e1, e2) = (0, 0, 0)
for i in range(x):
	if l[i] != e1 and l[i] != e2:
		if i < x - 1 and l[i + 1] == e2:
			c += 1
			e2 = l[i]
		else:
			c += 1
			e1 = l[i]
	elif l[i] != e1:
		c += 1
		e1 = l[i]
	elif l[i] != e2:
		c += 1
		e2 = l[i]
print(c)


n = int(input())
a1 = list(map(int, input().split()))
(tmp1, tmp2, ans1) = (0, 0, 0)
for i in range(n):
	if a1[i] == tmp1 and a1[i] == tmp2:
		continue
	elif a1[i] != tmp1 and a1[i] != tmp2:
		if i + 1 < n and a1[i + 1] == tmp1:
			tmp1 = a1[i]
		else:
			tmp2 = a1[i]
	elif a1[i] != tmp1:
		tmp1 = a1[i]
	elif a1[i] != tmp2:
		tmp2 = a1[i]
	ans1 += 1
print(ans1)


def compact(array):
	result = []
	array.append(-1)
	start = 0
	for i in range(len(array) - 1):
		if array[i] != array[i + 1]:
			result.append((array[i], i - start + 1))
			start = i + 1
	return result
n = int(input())
a = list(map(int, input().split()))
data = compact(a)
result = 0
last_group = -1
between = []
for (el, cnt) in data:
	if cnt == 1:
		result += 1
		between.append(el)
	else:
		if last_group != el:
			result += 2
		elif len(between) > 0 and (len(between) % 2 == 1 and between.count(el) >= (len(between) - 1) // 2) or len(between) == 1:
			result += 1
		else:
			result += 2
		between = []
		last_group = el
print(result)


def segmenti(a, n):
	if n == 0:
		print('0')
	elif n == 1:
		print('1')
	elif n == 2:
		print('2')
	else:
		beli = ['brt']
		nb = 1
		crni = ['brt']
		nc = 1
		i = 0
		seg = 0
		while i < n - 1:
			if beli[nb - 1] == crni[nc - 1]:
				if beli[nb - 1] != a[i]:
					seg += 1
				beli.append(a[i])
				nb += 1
			elif a[i] == a[i + 1]:
				if a[i] != beli[nb - 1]:
					beli.append(a[i])
					nb += 1
					seg += 1
				else:
					seg += 1
					crni.append(a[i])
					nc += 1
			elif a[i] == beli[nb - 1]:
				seg += 1
				crni.append(a[i])
				nc += 1
			elif a[i] == crni[nc - 1]:
				seg += 1
				beli.append(a[i])
				nb += 1
			elif a[i + 1] == beli[nb - 1]:
				seg += 1
				beli.append(a[i])
				nb += 1
			else:
				seg += 1
				crni.append(a[i])
				nc += 1
			i += 1
		if a[i] != beli[nb - 1] or a[i] != crni[nc - 1]:
			seg += 1
		print(seg)
n = int(input())
a = input().split()
a = [int(i) for i in a]
segmenti(a, n)


input()
arr = [int(x) for x in input().split()] + [None]
seg1 = None
seg2 = None
score = 0
for (i, a) in enumerate(arr):
	if arr[i] == None:
		break
	if arr[i + 1] != a:
		if arr[i + 1] == seg1 and seg1 != a:
			seg1 = a
			score += 1
			continue
		elif arr[i + 1] == seg2 and seg2 != a:
			seg2 = a
			score += 1
			continue
	if seg1 != a:
		score += 1
		seg1 = a
	elif seg2 != a:
		score += 1
		seg2 = a
print(score)


from sys import stdin
input = stdin.readline

def main():
	n = int(input())
	ara = [int(x) for x in input().split()]
	positions = [[] for i in range(n + 1)]
	for idx in range(n):
		positions[ara[idx]].append(idx)
	next_ara = [n] * (n + 1)
	for idx in range(n + 1):
		size = len(positions[idx])
		for jdx in range(size):
			if jdx < size - 1:
				next_ara[positions[idx][jdx]] = positions[idx][jdx + 1]
			else:
				next_ara[positions[idx][jdx]] = n
	ara.append(n + n)
	ones = [n]
	zeros = [n]
	ans = 0
	for idx in range(n):
		if ara[idx] == ara[ones[-1]] and ara[idx] == ara[zeros[-1]]:
			ones.append(idx)
		elif ara[idx] == ara[ones[-1]]:
			zeros.append(idx)
			ans += 1
		elif ara[idx] == ara[zeros[-1]]:
			ones.append(idx)
			ans += 1
		elif next_ara[ones[-1]] < next_ara[zeros[-1]]:
			ones.append(idx)
			ans += 1
		else:
			zeros.append(idx)
			ans += 1
	print(ans)
main()


import sys
n = int(input())
a = list(map(int, input().split()))
pre = []
last = a[0]
count = 0
for i in range(n):
	if last == a[i]:
		count += 1
		continue
	else:
		pre.append((last, count))
		last = a[i]
		count = 1
pre.append((last, count))
b = -1
w = -1
ans = 0
for i in range(len(pre)):
	val = pre[i][0]
	count = pre[i][1]
	if count > 1:
		if b != val and w != val:
			ans += 2
			b = val
			w = val
		elif b == val:
			w = val
			ans += 1
		elif w == val:
			b = val
			ans += 1
	elif b == val and w == val:
		pass
	elif b == val:
		w = val
		ans += 1
	elif w == val:
		b = val
		ans += 1
	elif i + 1 < len(pre):
		val2 = pre[i + 1][0]
		count2 = pre[i + 1][1]
		if b == val2:
			b = val
			ans += 1
		elif w == val2:
			w = val
			ans += 1
		else:
			b = val
			ans += 1
	else:
		b = val
		ans += 1
print(ans)


n = int(input())
a = [0] * 400000
seg = [0] * 400000
lenSeg = [0] * 400000
row = input()
row = row.split(' ')
cnt = 0
for i in range(0, n + 1):
	if i != n:
		a[i] = int(row[i])
	else:
		a[i] = -1
	if i != 0 and a[i] != a[i - 1]:
		seg[cnt] = a[i - 1]
		cnt += 1
	lenSeg[cnt] += 1
res = 0
mid = -1
long = -1
for i in range(0, cnt):
	if lenSeg[i] == 1:
		res += 1
	elif lenSeg[i] > 1:
		if long != -1 and seg[long] == seg[i]:
			if long < mid:
				res += 2
			else:
				res += 1
		if seg[long] != seg[i] or long == -1:
			res += 2
		long = i
	if seg[i + 1] != seg[i - 1] and i < cnt - 1 and (seg[i] != seg[long]) and (lenSeg[i] == 1):
		mid = i
print(res)


from collections import defaultdict
n = int(input())
l = list(map(int, input().split()))
s = 0
d = defaultdict(list)
for i in range(n + 1):
	d[i].append(10 ** 5 + 1)
for i in range(n - 1, -1, -1):
	d[l[i]].append(i)
a = 0
b = 0
cnt = 0
for i in range(n):
	d[l[i]].pop()
	if l[i] == a and l[i] == b:
		b = l[i]
	elif l[i] == a:
		b = l[i]
		cnt += 1
	elif l[i] == b:
		a = l[i]
		cnt += 1
	else:
		if d[a][-1] < d[b][-1]:
			a = l[i]
		else:
			b = l[i]
		cnt += 1
print(cnt)


from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
nx_pos = [float('inf')] * n
dic = defaultdict(lambda : float('inf'))
for i in range(n - 1, -1, -1):
	nx_pos[i] = dic[a[i]]
	dic[a[i]] = i
(b, w) = ([(-1, -1)], [(-1, -1)])
ans = 0
for i in range(n):
	x = a[i]
	if b[-1][0] == x and w[-1][0] != x:
		w.append((x, i))
		ans += 1
	elif w[-1][0] == x and b[-1][0] != x:
		b.append((x, i))
		ans += 1
	elif w[-1][0] != x and b[-1][0] != x:
		na = nx_pos[b[-1][1]]
		nb = nx_pos[w[-1][1]]
		if na > nb:
			w.append((x, i))
		else:
			b.append((x, i))
		ans += 1
	else:
		w.append((x, i))
print(ans)


n = int(input())
aa = [int(x) for x in input().split()]
segcount = 0
choices = {(-1, -1)}
for i in range(n):
	a = aa[i]
	new_choices = set()
	have_plus = False
	num_awhite = 0
	num_ablack = 0
	for choice in choices:
		(last_white, last_black) = choice
		if num_awhite <= 2 and a != last_white:
			have_plus = True
			new_choices.add((a, last_black))
			num_awhite += 1
		if num_ablack <= 2 and a != last_black:
			have_plus = True
			new_choices.add((last_white, a))
			num_ablack += 1
	if have_plus == True:
		segcount += 1
		choices = new_choices
print(segcount)


from collections import deque
from typing import List

class ContestParser:

	def __init__(self):
		self.buffer = deque()

	def next_token(self) -> str:
		if len(self.buffer) == 0:
			self.buffer.extend(input().split())
		return self.buffer.popleft()

	def next_int(self) -> int:
		return int(self.next_token())
parser = ContestParser()
n = parser.next_int()
states = [(0, 0)]
best_v = 0
for i in range(n):
	x = parser.next_int()
	new_states = []
	need_change = False
	for (a, b) in states:
		if x != a or x != b:
			need_change = True
	if need_change:
		best_v += 1
		s = set()
		for (a, b) in states:
			if x == a:
				continue
			if len(s) > 3:
				continue
			if b in s:
				continue
			s.add(b)
			new_states.append((x, b))
		s = set()
		for (a, b) in states:
			if x == b:
				continue
			if len(s) > 3:
				continue
			if a in s:
				continue
			s.add(a)
			new_states.append((a, x))
		states = new_states
	else:
		new_states = states
print(best_v)