Paint the Middle (Codeforces 1631E)
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):
from collections import defaultdict
from sys import stdin, gettrace
if gettrace():

    def inputi():
        return input()
else:

    def input():
        return next(stdin)[:-1]

    def inputi():
        return stdin.buffer.readline()

def solve(n, aa):
    start = {}
    end = {}
    for (i, a) in enumerate(aa):
        start[a] = min(start.get(a, n), i)
        end[a] = max(end.get(a, -1), i)
    s = -1
    e = -1
    res = 0
    cnt = 1
    intervals = []
    for a in start:
        if start[a] > e:
            if s < e:
                cnt = 1
                cs = s
                ce = s
                for (ist, ie) in intervals:
                    if ist > cs:
                        cnt += 1
                        cs = ce
                    ce = max(ie, ce)
                    if ce >= e:
                        break
                res += e - s - cnt
            s = start[a]
            e = end[a]
            intervals = [[start[a], end[a]]]
            cnt = 1
        else:
            if end[a] > e:
                e = end[a]
                cnt += 1
            intervals.append([start[a], end[a]])
    if s < e:
        cnt = 1
        cs = s
        ce = s
        for (ist, ie) in intervals:
            if ist > cs:
                cnt += 1
                cs = ce
            ce = max(ie, ce)
            if ce >= e:
                break
        res += e - s - cnt
    return res

def main():
    n = int(input())
    aa = [int(a) for a in input().split()]
    print(solve(n, aa))
if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin, stdout
n = int(stdin.readline())
a = [int(x) for x in stdin.readline().split()]
last = {}
for i in range(n):
    last[a[i]] = i
unpainted = 0
pointer = 0
current_right = -1
best_right = -1
while pointer < n:
    if pointer < current_right:
        best_right = max(best_right, last[a[pointer]])
        pointer += 1
    elif pointer == current_right:
        if best_right == current_right:
            unpainted += num_intervals + 1
            pointer += 1
        else:
            current_right = best_right
            num_intervals += 1
            pointer += 1
    elif last[a[pointer]] == pointer:
        unpainted += 1
        pointer += 1
    else:
        current_right = last[a[pointer]]
        best_right = last[a[pointer]]
        num_intervals = 1
        pointer += 1
stdout.write(str(n - unpainted) + '\n')

Solution (Python):
n = int(input())
A = input().split(' ')
A = [int(i) for i in A]
last = [-1] * (n + 1)
for i in range(len(A)):
    act = A[i]
    last[act] = i
inv_sol = 0
pointer1 = pointer2 = -1
for i in range(len(A)):
    act = A[i]
    if pointer1 > i:
        pointer2 = max(pointer2, last[act])
    elif pointer1 == i:
        inv_sol += 1
        pointer1 = pointer2
    else:
        inv_sol += 1
        if last[act] > i:
            pointer1 = last[act]
print(n - inv_sol)