Problem:
 Score : 600 points    Problem Statement We have 3N cards arranged in a row from left to right, where each card has an integer between 1 and N (inclusive) written on it. The integer written on the i -th card from the left is A_i .  You will do the following operation N-1 times:   Rearrange the five leftmost cards in any order you like, then remove the three leftmost cards. If the integers written on those three cards are all equal, you gain 1 point.   After these N-1 operations, if the integers written on the remaining three cards are all equal, you will gain 1 additional point.  Find the maximum number of points you can gain.      Constraints  1 \leq N \leq 2000  1 \leq A_i \leq N         Input Input is given from Standard Input in the following format:  N  A_1  A_2  \cdots  A_{3N}       Output Print the maximum number of points you can gain.        Sample Input 1 2
1 2 1 2 2 1      Sample Output 1 2  Let us rearrange the five leftmost cards so that the integers written on the six cards will be 2\ 2\ 2\ 1\ 1\ 1 from left to right.  Then, remove the three leftmost cards, all of which have the same integer 2 , gaining 1 point.  Now, the integers written on the remaining cards are 1\ 1\ 1 .  Since these three cards have the same integer 1 , we gain 1 more point.  In this way, we can gain 2 points - which is the maximum possible.       Sample Input 2 3
1 1 2 2 3 3 3 2 1      Sample Output 2 1       Sample Input 3 3
1 1 2 2 2 3 3 3 1      Sample Output 3 3

Solution (Python):
import sys

sys.setrecursionlimit(10**6)
int1 = lambda x: int(x)-1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n = II()
aa = LI1()
dp = [[-10]*n for _ in range(n)]
mx = [-10]*(n+1)
nmx = [-10]*(n+1)
a, b = min(aa[:2]), max(aa[:2])
dp[a][b] = dp[b][a] = 0
mx[a] = mx[b] = mx[n] = 0

def chmax(i, j, val):
    if val < 0: return
    if val > dp[i][j]:
        dp[i][j] = dp[j][i] = val
        nmx[i] = max(nmx[i], val)
        nmx[j] = max(nmx[j], val)
        nmx[n] = max(nmx[n], val)

base = 0
for i in range(n-1):
    abc = aa[i*3+2:i*3+5]
    
    abc.sort()
    a, b, c = abc
    
    if a == c:
        base += 1
        continue
    
    if b == c: a, c = c, a
    
    if a == b:
        vc = dp[c][c]
        for x, v in enumerate(dp[a][:]): chmax(c, x, v+1)
        chmax(a, c, max(mx[n], dp[a][a]+1))
        chmax(a, a, max(mx[n], vc+1))
        for x in range(n): chmax(a, x, mx[x])
        for x in range(n): chmax(c, x, mx[x])
    
    else:
        
        chmax(b, c, max(dp[a][a]+1, mx[n]))
        chmax(a, c, max(dp[b][b]+1, mx[n]))
        chmax(a, b, max(dp[c][c]+1, mx[n]))
        
        for x in range(n):
            chmax(a, x, mx[x])
            chmax(b, x, mx[x])
            chmax(c, x, mx[x])

    for x in range(n+1): mx[x] = max(mx[x], nmx[x])
    
    
    

a = aa[-1]
ans = max(mx[n], dp[a][a]+1)+base
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

ANS=0
B=[A[0],A[1]]
C=[]
D=A[-1]

for i in range(N-1):
    if A[i*3+2]==A[i*3+3]==A[i*3+4]:
        ANS+=1
    else:
        C.append((A[i*3+2],A[i*3+3],A[i*3+4]))

DP=[[-1]*(N+1) for i in range(N+1)]
MAXDP=[-1]*(N+1)
SCMAX=0

DP[B[0]][B[1]]=DP[B[1]][B[0]]=0
MAXDP[B[0]]=0
MAXDP[B[1]]=0

for x,y,z in C:
    
    
    
    
    

    NLIST=[]
    SCMAX2=0

    NMAXDP=[i for i in MAXDP]

    xy=max(0,DP[x][y],DP[z][z]+1)
    yz=max(0,DP[y][z],DP[x][x]+1)
    zx=max(0,DP[z][x],DP[y][y]+1)
    
    if x==y:
        for i in range(N+1):
            if DP[i][x]!=-1:
                NLIST.append((i,z,max(DP[i][z],DP[i][x]+1)))
                
         
            NMAXDP[i]=max(NMAXDP[i],DP[i][z],DP[z][i])
            NMAXDP[z]=max(NMAXDP[z],DP[i][z],DP[z][i])

    if y==z:
        for i in range(N+1):
            if DP[i][y]!=-1:
                NLIST.append((i,x,max(DP[i][x],DP[i][y]+1)))
                
                
            NMAXDP[i]=max(NMAXDP[i],DP[i][x],DP[x][i])
            NMAXDP[x]=max(NMAXDP[x],DP[i][x],DP[x][i])

    if z==x:
        for i in range(N+1):
            if DP[i][x]!=-1:
                NLIST.append((i,y,max(DP[i][y],DP[i][x]+1)))
                
                
            NMAXDP[i]=max(NMAXDP[i],DP[i][y],DP[y][i])
            NMAXDP[y]=max(NMAXDP[y],DP[i][y],DP[y][i])

    for i,j,sc in NLIST:
        DP[i][j]=DP[j][i]=max(DP[i][j],sc)
        SCMAX2=max(SCMAX,DP[i][j])

    
    
    

    for i in range(N+1):
        DP[i][x]=DP[x][i]=max(DP[i][x],MAXDP[i])
        DP[i][y]=DP[y][i]=max(DP[i][y],MAXDP[i])
        DP[i][z]=DP[z][i]=max(DP[i][z],MAXDP[i])
        SCMAX2=max(SCMAX2,DP[i][x],DP[i][y],DP[i][z])
                   
        NMAXDP[i]=max(NMAXDP[i],DP[i][x],DP[i][y],DP[i][z])
        NMAXDP[x]=max(NMAXDP[x],DP[i][x])
        NMAXDP[y]=max(NMAXDP[y],DP[i][y])
        NMAXDP[z]=max(NMAXDP[z],DP[i][z])

    DP[x][y]=DP[y][x]=max(SCMAX,xy)
    DP[y][z]=DP[z][y]=max(SCMAX,yz)
    DP[z][x]=DP[x][z]=max(SCMAX,zx)
    SCMAX2=max(SCMAX2,DP[x][y],DP[y][z],DP[z][x])

    MAXDP=NMAXDP
    MAXDP[x]=max(MAXDP[x],DP[x][y],DP[y][x],DP[z][x],DP[x][z])
    MAXDP[y]=max(MAXDP[y],DP[x][y],DP[y][x],DP[z][y],DP[y][z])
    MAXDP[z]=max(MAXDP[z],DP[x][z],DP[z][x],DP[z][y],DP[y][z])
    SCMAX=SCMAX2




DP[D][D]+=1

DPANS=0
for d in DP:
    DPANS=max(max(d),DPANS)

print(ANS+DPANS)

Solution (Python):
def insertR(a, b):
  if a not in R: R[a] = {}
  if b not in R[a]: R[a][b] = 0

N = int(input())
A = list(map(int, input().split()))

if N == 1:
  print(1)
  exit()

DP = [[-1] * (N + 1) for _ in range(N + 1)]
D = [-1] * (N + 1)
R = {}
for i in range(5):
  a = A[i]
  if a in R:
    R[a] += 1
  else:
    R[a] = 1

Flag = 0
for i in R.keys():
  if R[i] >= 3:
    Flag = 1
    R[i] -= 3

L = []
for i in R.keys():
  if R[i] == 2:
    L.append(i)
    DP[i][i] = Flag
    D[i] = Flag
  elif R[i] == 1:
    L.append(i)
    D[i] = Flag

for i in range(len(L) - 1):
  for j in range(i + 1, len(L)):
    DP[L[i]][L[j]] = Flag

common = 0
for i in range(5, N * 3 - 3, 3):
  L = []
  for j in range(i, i + 3):
    for k in range(len(L)):
      if L[k][1] == A[j]:
        L[k][0] += 1
        break
    else :
      L.append([1, A[j]])
  L.sort()
  R = {}
  
  if len(L) == 1:
    common += 1
  
  elif len(L) == 2:
    a = L[0][1]
    b = L[1][1]
    
    if DP[a][a] != -1:
      insertR(b, b)
      R[b][b] = max([R[b][b], DP[b][b], DP[a][a] + 1])
    
    for j in range(N + 1):
      n = max(DP[b][j], DP[j][b])
      if n == -1: continue
      insertR(a, j)
      R[a][j] = max([R[a][j], DP[a][j], n + 1])
    
    for j in range(N + 1):
      n = D[j]
      if n == -1: continue
      insertR(a, j)
      R[a][j] = max(R[a][j], n)
      insertR(b, j)
      R[b][j] = max(R[b][j], n)
    n = max(D)
    insertR(a, b)
    R[a][b] = max(R[a][b], n)
    insertR(b, b)
    R[b][b] = max(R[b][b], n)
  
  elif len(L) == 3:
    a = L[0][1]
    b = L[1][1]
    c = L[2][1]
    insertR(b, c)
    insertR(a, c)
    insertR(a, b)
    
    if DP[a][a] != -1:  
      R[b][c] = max(R[b][c], DP[a][a] + 1)
    if DP[b][b] != -1:      
      R[a][c] = max(R[a][c], DP[b][b] + 1)
    if DP[c][c] != -1:
      R[a][b] = max(R[a][b], DP[c][c] + 1)
    
    for j in range(N + 1):
      n = D[j]
      if n == -1: continue
      insertR(a, j)
      R[a][j] = max(R[a][j], n)
      insertR(b, j)
      R[b][j] = max(R[b][j], n)
      insertR(c, j)
      R[c][j] = max(R[c][j], n)
    n = max(D)
    R[a][b] = max(R[a][b], n)
    R[b][c] = max(R[b][c], n)
    R[a][c] = max(R[a][c], n)

  for k in R.keys():
    for kk in R[k].keys():
      n = R[k][kk]
      DP[k][kk] = max(DP[k][kk], n)
      DP[kk][k] = max(DP[kk][k], n)
      D[k] = max(D[k], n)
      D[kk] = max(D[kk], n)

a = A[-1]
if DP[a][a] != -1:
  DP[a][a] += 1

ans = 0
for i in DP:
  for j in i:
    ans = max(ans, j)

ans += common

print(ans)

Solution (Python):
from collections import deque


def upd(a, b, v):
    global N
    dp[a][b] = max(dp[a][b], v)
    dp[b][a] = max(dp[b][a], v)
    dp[N][a] = max(dp[N][a], v)
    dp[N][b] = max(dp[N][b], v)
    dp[a][N] = max(dp[a][N], v)
    dp[b][N] = max(dp[b][N], v)
    dp[N][N] = max(dp[N][N], v)


N = int(input())
A = list(map(lambda x: int(x) - 1, input().split()))

INF = 1 << 32
dp = [[-INF] * (N + 1) for _ in range(N + 1)]
upd(A[0], A[1], 0)
base = 0
q = deque()

for i in range(2, 3 * N - 1, 3):
    x, y, z = A[i], A[i + 1], A[i + 2]
    if x == y == z:  
        base += 1
    else:
        for _ in range(3):
            
            for k in range(N):
                v = dp[k][N]
                if y == z:
                    v = max(v, dp[k][y] + 1)
                q.append((k, x, v))
            
            v = max(dp[z][z] + 1, dp[N][N])
            q.append((x, y, v))
            
            x, y, z = z, x, y
        while q:
            a, b, v = q.popleft()
            upd(a, b, v)

l = A[-1]
ans = max(dp[N][N], dp[l][l] + 1)
print(ans + base)

Solution (Python):
from collections import deque


def upd(a, b, v):
    global N
    dp[a][b] = max(dp[a][b], v)
    dp[b][a] = max(dp[b][a], v)
    dp[N][a] = max(dp[N][a], v)
    dp[N][b] = max(dp[N][b], v)
    dp[a][N] = max(dp[a][N], v)
    dp[b][N] = max(dp[b][N], v)
    dp[N][N] = max(dp[N][N], v)


N = int(input())
A = list(map(lambda x: int(x) - 1, input().split()))

INF = 1 << 32
dp = [[-INF] * (N + 1) for _ in range(N + 1)]
upd(A[0], A[1], 0)
base = 0

for i in range(2, 3 * N - 1, 3):
    x, y, z = A[i], A[i + 1], A[i + 2]
    if x == y == z:  
        base += 1
    else:
        q = deque()
        for _ in range(3):
            
            for k in range(N):
                v = dp[k][N]
                if y == z:
                    v = max(v, dp[k][y] + 1)
                q.append((k, x, v))
            
            v = max(dp[z][z] + 1, dp[N][N])
            q.append((x, y, v))
            
            x, y, z = z, x, y
        while q:
            a, b, v = q.popleft()
            upd(a, b, v)

l = A[-1]
ans = max(dp[N][N], dp[l][l] + 1)
print(ans + base)

Solution (Python):
from collections import deque


def upd(a, b, v):
    global N
    dp[a][b] = max(dp[a][b], v)
    dp[b][a] = max(dp[b][a], v)
    dp[N][a] = max(dp[N][a], v)
    dp[N][b] = max(dp[N][b], v)
    dp[a][N] = max(dp[a][N], v)
    dp[b][N] = max(dp[b][N], v)
    dp[N][N] = max(dp[N][N], v)


N = int(input())
A = list(map(lambda x: int(x) - 1, input().split()))

INF = 1 << 32
dp = [[-INF] * (N + 1) for _ in range(N + 1)]
upd(A[0], A[1], 0)
base = 0

for i in range(2, 3 * N - 1, 3):
    x, y, z = A[i], A[i + 1], A[i + 2]
    if x == y == z:  
        base += 1
    else:
        q = deque()
        for _ in range(3):
            for k in range(N):
                v = dp[k][N]
                if y == z:
                    v = max(v, dp[k][y] + 1)
                q.append((k, x, v))
            v = max(dp[z][z] + 1, dp[N][N])
            q.append((x, y, v))
            x, y, z = z, x, y
        while q:
            a, b, v = q.popleft()
            upd(a, b, v)

l = A[-1]
ans = max(dp[N][N], dp[l][l] + 1)
print(ans + base)

Solution (Python):
n = int(input())
A = list(map(int,input().split()))
dp = [[-float("INF")]*(n+1) for i in range(n+1)]
low = [-float("INF")]*(n+1)
m = 0
a,b = A[:2]
dp[a][b] = 0
dp[b][a] = 0
low[a] = 0
low[b] = 0
base = 0
for _ in range(1,n):
    a,b,c = A[3*_-1:3*_+2]
    q = []
    if a==b==c:
        base += 1
        continue
    m1 = m
    for j in range(3):
        q.append((a,b,max(m,dp[c][c]+1)))
        m1 = max(m1,dp[c][c]+1)
        for i in range(1,n+1):
            q.append((a,i,low[i]))
        if a==b:
            for i in range(1,n+1):
                q.append((c,i,dp[a][i]+1))
                m1 = max(m1,dp[a][i]+1)
        a,b,c = b,c,a
    for a,b,v in q:
        dp[a][b] = max(dp[a][b],v)
        dp[b][a] = max(dp[b][a],v)
        low[a] = max(low[a],v)  
        low[b] = max(low[b],v)      
    m = m1
print(max(m,dp[A[-1]][A[-1]]+1)+base)

Solution (Python):
n = int(input())
A = list(map(int,input().split()))

dp = [[-float("INF")]*(n+1) for i in range(n+1)]
low = [-float("INF")]*(n+1)
m = 0
a,b = A[:2]
dp[a][b] = 0
dp[b][a] = 0
low[a] = 0
low[b] = 0
base = 0

for _ in range(1,n):
    a,b,c = A[3*_-1:3*_+2]
    q = []
    if a==b==c:
        base += 1
        continue
    m1 = m
    for j in range(3):
        q.append((a,b,max(m,dp[c][c]+1)))
        m1 = max(m1,dp[c][c]+1)

        for i in range(1,n+1):
            q.append((a,i,low[i]))

        if a==b:
            for i in range(1,n+1):
                q.append((c,i,dp[a][i]+1))
                m1 = max(m1,dp[a][i]+1)
                
        a,b,c = b,c,a

    for a,b,v in q:
        dp[a][b] = max(dp[a][b],v)
        dp[b][a] = max(dp[b][a],v)
        low[a] = max(low[a],v)  
        low[b] = max(low[b],v)      
    m = m1
print(max(m,dp[A[-1]][A[-1]]+1)+base)

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    A = list(map(int,input().split()))
    
    dp = [[-float("INF")]*(n+1) for i in range(n+1)]
    low = [-float("INF")]*(n+1)
    m = 0
    a,b = A[:2]
    dp[a][b] = 0
    dp[b][a] = 0
    low[a] = 0
    low[b] = 0
    base = 0

    for _ in range(1,n):
        a,b,c = A[3*_-1:3*_+2]
        q = []
        if a==b==c:
            base += 1
            continue
        m1 = max(m,max(dp[a][a],dp[b][b],dp[c][c])+1)
        for j in range(3):
            q.append((a,b,max(m,dp[c][c]+1)))
            for i in range(1,n+1):
                q.append((a,i,low[i]))
            if a==b:
                for i in range(1,n+1):
                    q.append((c,i,dp[a][i]+1))
                    m1 = max(m1,dp[a][i]+1)
            a,b,c = b,c,a
        for a,b,v in q:
            dp[a][b] = max(dp[a][b],v)
            dp[b][a] = max(dp[b][a],v)
            low[a] = max(low[a],v)  
            low[b] = max(low[b],v)      
        m = m1
    print(max(m,dp[A[-1]][A[-1]]+1)+base)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int,input().split()))

dp = [[-float("INF")]*(n+1) for i in range(n+1)]
low = [-float("INF")]*(n+1)
m = 0
a,b = A[:2]
dp[a][b] = 0
dp[b][a] = 0
low[a] = 0
low[b] = 0
base = 0

for _ in range(1,n):
    a,b,c = A[3*_-1:3*_+2]
    q = []
    if a==b==c:
        base += 1
        continue
    m1 = max(m,max(dp[a][a],dp[b][b],dp[c][c])+1)
    for j in range(3):
        q.append((a,b,max(m,dp[c][c]+1)))
        for i in range(1,n+1):
            q.append((a,i,low[i]))
        if a==b:
            for i in range(1,n+1):
                q.append((c,i,dp[a][i]+1))
                m1 = max(m1,dp[a][i]+1)
        a,b,c = b,c,a
    for a,b,v in q:
        dp[a][b] = max(dp[a][b],v)
        dp[b][a] = max(dp[b][a],v)
        low[a] = max(low[a],v)  
        low[b] = max(low[b],v)      
    m = m1
print(max(m,dp[A[-1]][A[-1]]+1)+base)

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

from collections import defaultdict
sys.setrecursionlimit(10**7)









INF = 1 << 50
def run():
    N, *A_ = map(int, read().split())
    dp = [[-INF] * (N+1) for _ in range(N+1)]
    dp_max = [-INF] * (N+1)
    a, b = A_[:2]
    dp[a][b] = dp[b][a] = dp_max[a] = dp_max[b] = 0

    triplets = 0
    chunks = []

    for i in range(N-1):
        x,y,z = A_[3*i+2 : 3*i+5]
        if x == y == z:
            triplets+=1
        else:
            chunks.append((x,y,z))

    for x,y,z in chunks:
        cache = []
        
        if y == z:
            x,y,z = y,z,x
        elif z == x:
            x,y,z = z,x,y

        if x == y:
            for i in range(1, N+1):
                cache.append((z, i, dp[x][i] + 1))

        
        cache.append((y, z, dp[x][x] + 1))
        cache.append((z, x, dp[y][y] + 1))
        cache.append((x, y, dp[z][z] + 1))

        
        MAX = max(dp_max)
        cache.append((x, y, MAX))
        cache.append((y, z, MAX))
        cache.append((z, x, MAX))
        for i in range(1, N+1):
            cache.append((i, x, dp_max[i]))
            cache.append((i, y, dp_max[i]))
            cache.append((i, z, dp_max[i]))

        
        for a, b, value in cache:
            dp[a][b] = dp[b][a] = max(value, dp[a][b])
            dp_max[a] = max(dp_max[a], dp[a][b])
            dp_max[b] = max(dp_max[b], dp[a][b])

    a = A_[-1]
    dp[a][a] += 1
    dp_max[a] = max(dp[a][a], dp_max[a])

    print(max(dp_max) + triplets)
    


if __name__ == "__main__":
    run()

Solution (Python):
from typing import List


class DP:
    N: int
    table: List[List[int]]
    max_all: int
    max_arr: List[int]
    inc: int

    def __init__(self, N: int, x: int, y: int):
        self.N = N
        self.table = [[-(1 << 28)] * (N + 1) for _ in range(N + 1)]
        self.table[x][y] = self.table[y][x] = 0
        self.max_all = 0
        self.max_arr = [-(1 << 28)] * (N + 1)
        self.max_arr[x] = self.max_arr[y] = 0
        self.inc = 0

    def update(self, p: int, q: int, r: int) -> None:
        if p == q == r:
            self.inc += 1
            return

        npqr = self._update_pqr(p, q, r)
        nqrp = self._update_pqr(q, r, p)
        nrpq = self._update_pqr(r, p, q)

        npq = self._update_pq(p, q)
        nqr = self._update_pq(q, r)
        nrp = self._update_pq(r, p)

        np = self._update_p(p)
        nq = self._update_p(q)
        nr = self._update_p(r)

        pq, qr, rp = None, None, None

        if p == q:
            pq = self._update_pair(p, r)

        if q == r:
            qr = self._update_pair(q, p)

        if r == p:
            rp = self._update_pair(r, q)

        self._update_maximum(q, r, npqr)
        self._update_maximum(r, p, nqrp)
        self._update_maximum(p, q, nrpq)

        self._update_maximum(p, q, npq)
        self._update_maximum(q, r, nqr)
        self._update_maximum(r, p, nrp)

        for k in range(self.N + 1):
            self._update_maximum(k, p, np[k])
            self._update_maximum(k, q, nq[k])
            self._update_maximum(k, r, nr[k])

        if pq:
            for k in range(self.N + 1):
                self._update_maximum(k, r, pq[k])

        if qr:
            for k in range(self.N + 1):
                self._update_maximum(k, p, qr[k])

        if rp:
            for k in range(self.N + 1):
                self._update_maximum(k, q, rp[k])


    def _update_maximum(self, x: int, y: int, v: int) -> None:
        self.table[x][y] = self.table[y][x] = max(self.table[x][y], v)
        self.max_all = max(self.max_all, v)
        self.max_arr[x] = max(self.max_arr[x], v)
        self.max_arr[y] = max(self.max_arr[y], v)

    def _update_pair(self, p: int, q: int) -> List[int]:
        return [max(self.table[k][q], self.table[k][p] + 1, self.table[p][k] + 1) for k in range(self.N + 1)]

    def _update_pqr(self, p: int, q: int, r: int) -> int:
        return max(self.table[q][r], self.table[p][p] + 1)

    def _update_pq(self, p: int, q: int) -> int:
        return max(self.table[p][q], self.max_all)

    def _update_p(self, p) -> List[int]:
        return [max(self.table[p][k], self.table[k][p], self.max_arr[k]) for k in range(self.N + 1)]

    def ans(self):
        return self.max_all + self.inc


N = int(input())
A = list(map(int, input().split())) + [0, 0]

dp = DP(N, A[0], A[1])

for i in range(N):
    Z = A[3 * i + 2: 3 * i + 5]
    dp.update(Z[0], Z[1], Z[2])
    

print(dp.ans())

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input().strip())+2
A = list(map(int,input().split()))+[N-1,N]
INF = N
dp = [[-INF for j in range(N)] for i in range(N)]
dpmax = -INF
dpmaxj = [-INF for i in range(N)]
score = 0
a,b,c,d,e = [i-1 for i in sorted(A[:5])]

if a == b == c:
  dp[d][e] = dp[e][d] = dpmaxj[d] = dpmaxj[e] = dpmax = 1
elif b == c == d:
  dp[a][e] = dp[e][a] = dpmaxj[a] = dpmaxj[e] = dpmax = 1
elif c == d == e:
  dp[a][b] = dp[b][a] = dpmaxj[a] = dpmaxj[b] = dpmax = 1
else:
  L = [a,b,c,d,e]
  for i in range(5):
    for j in range(i+1,5):
      p,q = L[i],L[j]
      dp[p][q] = dp[q][p] = dpmaxj[p] = dpmaxj[q] = 0
  dpmax = 0 

def update(i,j):
  dpmaxj[i] = max(dpmaxj[i],dp[i][j])
  dpmaxj[j] = max(dpmaxj[j],dp[i][j])

for i in range(N-3):
  prevdpmax = dpmax
  prevdpmaxj = dpmaxj[:]
  dpd = [dp[k][k] for k in range(N)]
  a,b,c = A[i*3+5:i*3+8]
  a -= 1
  b -= 1
  c -= 1
  prevdpka = [dp[i][a] for i in range(N)]
  prevdpla = [dp[a][i] for i in range(N)] 
  prevdpkb = [dp[i][b] for i in range(N)]
  prevdplb = [dp[b][i] for i in range(N)] 
  if a == b == c:
    score += 1
    continue
  elif a == b:
    for k in range(N):
      dp[k][c] = max(dp[k][c],max(prevdpka[k],prevdpla[k]) + 1); update(k,c)
      dp[c][k] = max(dp[c][k],max(prevdpka[k],prevdpla[k]) + 1); update(c,k)
      dpmax = max(dpmax,dp[k][c],dp[c][k])
  elif a == c:
    for k in range(N):
      dp[k][b] = max(dp[k][b],max(prevdpka[k],prevdpla[k]) + 1); update(k,b)
      dp[b][k] = max(dp[b][k],max(prevdpka[k],prevdpla[k]) + 1); update(b,k)
      dpmax = max(dpmax,dp[k][b],dp[b][k])
  elif b == c:
    for k in range(N):
      dp[k][a] = max(dp[k][a],max(prevdpkb[k],prevdplb[k]) + 1); update(k,a)
      dp[a][k] = max(dp[a][k],max(prevdpkb[k],prevdplb[k]) + 1); update(a,k)
      dpmax = max(dpmax,dp[k][a],dp[a][k])
  
  dp[b][c] = max(dp[b][c],dpd[a] + 1); update(b,c)
  dp[c][b] = max(dp[c][b],dpd[a] + 1); update(c,b)
  dp[a][c] = max(dp[a][c],dpd[b] + 1); update(a,c)
  dp[c][a] = max(dp[c][a],dpd[b] + 1); update(c,a)
  dp[a][b] = max(dp[a][b],dpd[c] + 1); update(a,b)
  dp[b][a] = max(dp[b][a],dpd[c] + 1); update(b,a)
  dpmax = max(dpmax,dp[b][c],dp[a][c],dp[a][b],dp[c][b],dp[c][a],dp[b][a])
  
  dp[a][b] = max(0,dp[a][b],prevdpmax); update(a,b)
  dp[b][a] = max(0,dp[b][a],prevdpmax); update(b,a)
  dp[b][c] = max(0,dp[b][c],prevdpmax); update(b,c)
  dp[c][b] = max(0,dp[c][b],prevdpmax); update(c,b)
  dp[a][c] = max(0,dp[a][c],prevdpmax); update(a,c)
  dp[c][a] = max(0,dp[c][a],prevdpmax); update(c,a)

  for j in range(N):
    dp[j][a] = max(dp[j][a],prevdpmaxj[j]); update(j,a)
    dp[j][b] = max(dp[j][b],prevdpmaxj[j]); update(j,b)
    dp[j][c] = max(dp[j][c],prevdpmaxj[j]); update(j,c)
    dp[a][j] = max(dp[a][j],prevdpmaxj[j]); update(a,j)
    dp[b][j] = max(dp[b][j],prevdpmaxj[j]); update(b,j)
    dp[c][j] = max(dp[c][j],prevdpmaxj[j]); update(c,j)
    
print(max(dp[N-2][N-1],dp[N-1][N-2])+score)

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input().strip())+2
A = list(map(int,input().split()))+[N-1,N]
INF = N
dp = [[-INF for j in range(N)] for i in range(N)]
dpmax = -INF
dpmaxj = [-INF for i in range(N)]
score = 0
a,b,c,d,e = [i-1 for i in sorted(A[:5])]

if a == b == c:
  dp[d][e] = dp[e][d] = dpmaxj[d] = dpmaxj[e] = dpmax = 1
elif b == c == d:
  dp[a][e] = dp[e][a] = dpmaxj[a] = dpmaxj[e] = dpmax = 1
elif c == d == e:
  dp[a][b] = dp[b][a] = dpmaxj[a] = dpmaxj[b] = dpmax = 1
else:
  L = [a,b,c,d,e]
  for i in range(5):
    for j in range(i+1,5):
      p,q = L[i],L[j]
      dp[p][q] = dp[q][p] = dpmaxj[p] = dpmaxj[q] = 0
  dpmax = 0 

def update(i,j):
  dpmaxj[i] = max(dpmaxj[i],dp[i][j])
  dpmaxj[j] = max(dpmaxj[j],dp[i][j])

for i in range(N-3):
  prevdpmax = dpmax
  prevdpmaxj = dpmaxj[:]
  dpd = [dp[k][k] for k in range(N)]
  a,b,c = A[i*3+5:i*3+8]
  a -= 1
  b -= 1
  c -= 1
  prevdpka = [dp[i][a] for i in range(N)]
  prevdpla = [dp[a][i] for i in range(N)] 
  prevdpkb = [dp[i][b] for i in range(N)]
  prevdplb = [dp[b][i] for i in range(N)] 
  if a == b == c:
    score += 1
    continue
  elif a == b:
    for k in range(N):
      dp[k][c] = max(dp[k][c],max(prevdpka[k],prevdpla[k]) + 1)
      dp[c][k] = max(dp[c][k],max(prevdpka[k],prevdpla[k]) + 1)
      dpmax = max(dpmax,dp[k][c],dp[c][k])
      update(k,c)
      update(c,k)
  elif a == c:
    for k in range(N):
      dp[k][b] = max(dp[k][b],max(prevdpka[k],prevdpla[k]) + 1)
      dp[b][k] = max(dp[b][k],max(prevdpka[k],prevdpla[k]) + 1)
      dpmax = max(dpmax,dp[k][b],dp[b][k])
      update(k,b)
      update(b,k)
  elif b == c:
    for k in range(N):
      dp[k][a] = max(dp[k][a],max(prevdpkb[k],prevdplb[k]) + 1)
      dp[a][k] = max(dp[a][k],max(prevdpkb[k],prevdplb[k]) + 1)
      dpmax = max(dpmax,dp[k][a],dp[a][k])
      update(k,a)
      update(a,k)
  dp[b][c] = max(dp[b][c],dpd[a] + 1)
  dp[c][b] = max(dp[c][b],dpd[a] + 1)
  dp[a][c] = max(dp[a][c],dpd[b] + 1)
  dp[c][a] = max(dp[c][a],dpd[b] + 1)
  dp[a][b] = max(dp[a][b],dpd[c] + 1)
  dp[b][a] = max(dp[b][a],dpd[c] + 1)
  dpmax = max(dpmax,dp[b][c],dp[a][c],dp[a][b],dp[c][b],dp[c][a],dp[b][a])
  
  dp[a][b] = max(0,dp[a][b],prevdpmax)
  dp[b][a] = max(0,dp[b][a],prevdpmax)
  dp[b][c] = max(0,dp[b][c],prevdpmax)
  dp[c][b] = max(0,dp[c][b],prevdpmax)
  dp[a][c] = max(0,dp[a][c],prevdpmax)
  dp[c][a] = max(0,dp[c][a],prevdpmax)
  update(a,b)
  update(a,c)
  update(b,a)
  update(b,c)
  update(c,a)
  update(c,b)
  for j in range(N):
    dp[j][a] = max(dp[j][a],prevdpmaxj[j])
    dp[j][b] = max(dp[j][b],prevdpmaxj[j])
    dp[j][c] = max(dp[j][c],prevdpmaxj[j])
    dp[a][j] = max(dp[a][j],prevdpmaxj[j])
    dp[b][j] = max(dp[b][j],prevdpmaxj[j])
    dp[c][j] = max(dp[c][j],prevdpmaxj[j])
    update(j,a)
    update(j,b)
    update(j,c)
    update(a,j)
    update(b,j)
    update(c,j)

print(max(dp[N-2][N-1],dp[N-1][N-2])+score)

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input().strip())+2
A = list(map(int,input().split()))+[N-1,N]
INF = N
dp = [[-INF for j in range(N)] for i in range(N)]
dpmax = -INF
dpmaxj = [-INF for i in range(N)]
score = 0
a,b,c,d,e = sorted(A[:5])
a -= 1
b -= 1
c -= 1
d -= 1
e -= 1

if a == b == c:
  dp[d][e] = 1
  dp[e][d] = 1
  dpmaxj[d] = 1
  dpmaxj[e] = 1
  dpmax = 1
elif b == c == d:
  dp[a][e] = 1
  dp[e][a] = 1
  dpmaxj[a] = 1
  dpmaxj[e] = 1
  dpmax = 1
elif c == d == e:
  dp[a][b] = 1
  dp[b][a] = 1
  dpmaxj[a] = 1
  dpmaxj[b] = 1
  dpmax = 1
else:
  L = [a,b,c,d,e]
  for i in range(5):
    for j in range(i+1,5):
      p,q = L[i],L[j]
      dp[p][q] = 0
      dp[p][q] = 0
      dpmaxj[p] = 0
      dpmaxj[q] = 0
  dpmax = 0 

def update(i,j):
  dpmaxj[i] = max(dpmaxj[i],dp[i][j])
  dpmaxj[j] = max(dpmaxj[j],dp[i][j])

for i in range(N-3):
  prevdpmax = dpmax
  prevdpmaxj = dpmaxj[:]
  dpd = [dp[k][k] for k in range(N)]
  a,b,c = A[i*3+5:i*3+8]
  a -= 1
  b -= 1
  c -= 1
  prevdpka = [dp[i][a] for i in range(N)]
  prevdpla = [dp[a][i] for i in range(N)] 
  prevdpkb = [dp[i][b] for i in range(N)]
  prevdplb = [dp[b][i] for i in range(N)] 
  if a == b == c:
    score += 1
    continue
  elif a == b:
    for k in range(N):
      dp[k][c] = max(dp[k][c],max(prevdpka[k],prevdpla[k]) + 1)
      dp[c][k] = max(dp[c][k],max(prevdpka[k],prevdpla[k]) + 1)
      dpmax = max(dpmax,dp[k][c],dp[c][k])
      update(k,c)
      update(c,k)
  elif a == c:
    for k in range(N):
      dp[k][b] = max(dp[k][b],max(prevdpka[k],prevdpla[k]) + 1)
      dp[b][k] = max(dp[b][k],max(prevdpka[k],prevdpla[k]) + 1)
      dpmax = max(dpmax,dp[k][b],dp[b][k])
      update(k,b)
      update(b,k)
  elif b == c:
    for k in range(N):
      dp[k][a] = max(dp[k][a],max(prevdpkb[k],prevdplb[k]) + 1)
      dp[a][k] = max(dp[a][k],max(prevdpkb[k],prevdplb[k]) + 1)
      dpmax = max(dpmax,dp[k][a],dp[a][k])
      update(k,a)
      update(a,k)
  dp[b][c] = max(dp[b][c],dpd[a] + 1)
  dp[c][b] = max(dp[c][b],dpd[a] + 1)
  dp[a][c] = max(dp[a][c],dpd[b] + 1)
  dp[c][a] = max(dp[c][a],dpd[b] + 1)
  dp[a][b] = max(dp[a][b],dpd[c] + 1)
  dp[b][a] = max(dp[b][a],dpd[c] + 1)
  dpmax = max(dpmax,dp[b][c],dp[a][c],dp[a][b],dp[c][b],dp[c][a],dp[b][a])
  
  dp[a][b] = max(0,dp[a][b],prevdpmax)
  dp[b][a] = max(0,dp[b][a],prevdpmax)
  dp[b][c] = max(0,dp[b][c],prevdpmax)
  dp[c][b] = max(0,dp[c][b],prevdpmax)
  dp[a][c] = max(0,dp[a][c],prevdpmax)
  dp[c][a] = max(0,dp[c][a],prevdpmax)
  update(a,b)
  update(a,c)
  update(b,a)
  update(b,c)
  update(c,a)
  update(c,b)
  for j in range(N):
    dp[j][a] = max(dp[j][a],prevdpmaxj[j])
    dp[j][b] = max(dp[j][b],prevdpmaxj[j])
    dp[j][c] = max(dp[j][c],prevdpmaxj[j])
    dp[a][j] = max(dp[a][j],prevdpmaxj[j])
    dp[b][j] = max(dp[b][j],prevdpmaxj[j])
    dp[c][j] = max(dp[c][j],prevdpmaxj[j])
    update(j,a)
    update(j,b)
    update(j,c)
    update(a,j)
    update(b,j)
    update(c,j)

print(max(dp[N-2][N-1],dp[N-1][N-2])+score)

Solution (Python):
def solve(n, aaa):
    NINF = -(10 ** 12)
    dp = [[NINF] * n for _ in range(n)]
    dp_max = [NINF] * n
    ans = 0

    a0, a1 = sorted(aaa[:2])
    dp[a0][a1] = 0
    dp_max[a0] = 0
    dp_max[a1] = 0

    for k in range(n - 1):
        a0, a1, a2 = sorted(aaa[2 + 3 * k:5 + 3 * k])
        if a0 == a1 and a1 == a2:
            ans += 1
            continue

        dp_max_max = max(dp_max)
        update_tasks = []

        if a0 == a1 or a1 == a2:
            rev = a1 == a2
            if rev:
                a0, a2 = a2, a0

            for b in range(n):
                c, d = min(a0, b), max(a0, b)
                e, f = min(a2, b), max(a2, b)
                update_tasks.append((e, f, dp_max[b]))
                update_tasks.append((e, f, dp[c][d] + 1))

            update_tasks.append((a0, a0, dp_max_max))
            update_tasks.append((a0, a0, dp[a2][a2] + 1))

            if rev:
                update_tasks.append((a2, a0, dp_max_max))
            else:
                update_tasks.append((a0, a2, dp_max_max))

        else:
            update_tasks.append((a0, a1, dp_max_max))
            update_tasks.append((a0, a2, dp_max_max))
            update_tasks.append((a1, a2, dp_max_max))
            update_tasks.append((a1, a2, dp[a0][a0] + 1))
            update_tasks.append((a0, a2, dp[a1][a1] + 1))
            update_tasks.append((a0, a1, dp[a2][a2] + 1))

            for b in range(n):
                b_max = dp_max[b]
                for a in (a0, a1, a2):
                    c, d = min(a, b), max(a, b)
                    update_tasks.append((c, d, b_max))

        for a, b, c in update_tasks:
            dp[a][b] = max(dp[a][b], c)
            dp_max[a] = max(dp_max[a], c)
            dp_max[b] = max(dp_max[b], c)

    a = aaa[-1]
    dp[a][a] += 1

    return max(map(max, dp)) + ans


n = int(input())
aaa = [a - 1 for a in map(int, input().split())]
ans = solve(n, aaa)
print(ans)