Painting the Array II
The only difference between the two versions is that this version asks the minimal 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 small as possible. Find this number.
In the first example, we can choose $$$a^{(0)} = [1,1,2,2]$$$, $$$a^{(1)} = [2,3]$$$ and $$$\mathit{seg}(a^{(0)}) = \mathit{seg}(a^{(1)}) = 2$$$. So the answer is $$$2+2 = 4$$$.In the second example, we can choose $$$a^{(0)} = [1,1,1,1]$$$, $$$a^{(1)} = [2,2,2]$$$ and $$$\mathit{seg}(a^{(0)}) = \mathit{seg}(a^{(1)}) = 1$$$. So the answer is $$$1+1 = 2$$$.
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 a single integer, indicating the minimal possible total number of segments.
import re
import functools
import random
import sys
import os
import math
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
import threading
import bisect
BUFSIZE = 4096
inf = float('inf')

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

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

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))

def dfs(graph, u, visited):
    queue = deque()
    queue.append(u)
    visited[u] = True
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if not visited[v]:
                visited[v] = True
                queue.append(v)

def dedup(arr):
    n = len(arr)
    (lo, ans) = (0, 0)
    while lo < n:
        hi = lo + 1
        while hi < n and arr[hi] == arr[lo]:
            hi += 1
        ans += 1
        lo = hi
    return ans - 1

def solve():
    n = II()
    arr = LII()
    locations = defaultdict(lambda : [n])
    for idx in range(n - 1, -1, -1):
        locations[arr[idx]].append(idx)
    locations[0].append(n + 1)
    (f, s) = ([0], [0])
    for (idx, val) in enumerate(arr):
        locations[val].pop()
        if val == f[-1]:
            f.append(val)
        elif val == s[-1]:
            s.append(val)
        elif locations[f[-1]][-1] <= locations[s[-1]][-1]:
            s.append(val)
        else:
            f.append(val)
    print(dedup(f) + dedup(s))
solve()
import sys
from collections import defaultdict

def main():
    n = int(sys.stdin.readline())
    a = sys.stdin.readline().split()
    data = []
    prev = {}
    result = 0
    current = [{'val': -1, 'prev': -1}, {'val': -1, 'prev': -1}]
    for (key, val) in enumerate(a):
        data.append({'val': val, 'prev': prev[val] if val in prev else -1})
        prev[val] = key
    for el in reversed(data):
        if el['val'] == current[0]['val']:
            current[0] = el
            continue
        if el['val'] == current[1]['val']:
            current[1] = el
            continue
        result += 1
        if current[0]['prev'] < current[1]['prev']:
            current[0] = el
        else:
            current[1] = el
    print(result)
    return
if __name__ == '__main__':
    main()
import sys
input = sys.stdin.buffer.readline

def process(A):
    n = len(A)
    S = set([])
    curr = 0
    for i in range(n):
        if i == 0 or A[i - 1] != A[i]:
            if A[i] in S:
                S = set([A[i], A[i - 1]])
            else:
                S.add(A[i])
                curr += 1
    return curr
n = int(input())
A = [int(x) for x in input().split()]
print(process(A))