Paint the Middle (Codeforces 1630C)
Tags: Greedy, two pointers

You are given $$$n$$$ elements numbered from $$$1$$$ to $$$n$$$, the element $$$i$$$ has value $$$a_i$$$ and color $$$c_i$$$, initially, $$$c_i = 0$$$ for all $$$i$$$.The following operation can be applied:  Select three elements $$$i$$$, $$$j$$$ and $$$k$$$ ($$$1 \leq i < j < k \leq n$$$), such that $$$c_i$$$, $$$c_j$$$ and $$$c_k$$$ are all equal to $$$0$$$ and $$$a_i = a_k$$$, then set $$$c_j = 1$$$. Find the maximum value of $$$\sum\limits_{i=1}^n{c_i}$$$ that can be obtained after applying the given operation any number of times.

Input: The first line contains an integer $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — the number of elements.The second line consists of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$), where $$$a_i$$$ is the value of the $$$i$$$-th element.

Output: Print a single integer in a line — the maximum value of $$$\sum\limits_{i=1}^n{c_i}$$$ that can be obtained after applying the given operation any number of times.

Note: In the first test, it is possible to apply the following operations in order:  

Sample Inputs:
7
1 2 1 2 7 4 7

13
1 2 3 2 1 3 3 4 5 5 5 4 7

Sample Outputs:
2

7

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]
last = {x: i for (i, x) in enumerate(a)}
(lastest, covered, ans) = (0, 0, 0)
for (i, x) in enumerate(a):
    lastest = max(lastest, last[x])
    if covered > i:
        ans += 1
    else:
        covered = lastest
print(ans)

Solution (Python):
I = lambda : [int(i) for i in input().split()]
n = int(input())
A = I()
a = {x: i for (i, x) in enumerate(A)}
(w, v, u) = (0, 0, 0)
for (i, x) in enumerate(A):
    w = max(w, a[x])
    if v > i:
        u += 1
    else:
        v = w
print(u)

Solution (Python):
import sys, io, os
try:
    Z = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
except:
    Z = lambda : sys.stdin.readline().encode()
Y = lambda : map(sub, Z().split())
sub = lambda x: int(x) - 1
n = int(Z())
a = [*Y()]
L = [-1] * n
for i in range(n):
    L[a[i]] = i
for x in range(n):
    if x != L[a[x]]:
        break
s = {a[x]}
ns = set()
r = 0
for i in range(x + 1, n):
    if s:
        if i == L[a[i]]:
            if a[i] in ns:
                ns.remove(a[i])
            elif a[i] in s:
                s.remove(a[i])
                if not s:
                    (s, ns) = (ns, set())
                    r -= 1
        elif a[i] not in s:
            ns.add(a[i])
        r += 1
    elif i != L[a[i]]:
        s.add(a[i])
print(r)