First of all, consider the DP (Dynamic Programming) where \(d[i][p][q]\) is defined as the maximum value of \(c\) when the operations up to \(k=i\) have finished, where \(x=p\) and \(y=q\). This DP has a spacial complexity of \(O(N^3)\), which does not finish within the memory and execution time limit, so we are going to optimize this DP.

First, note that \(\max(x,y)=\max(P_1,P_2,\ldots,P_k)\) for any \(k\). This allows us to remove one parameter from the DP above, and conduct a DP where \(d[i][p]\) is defined as the maximum value of \(c\) when the operations up to \(k=i\) have finished, where \(\min(x,y)=p\). (If no operations make \(\min(x,y)=p\), let it \(-\infty\).)

Let us consider the transition of this DP.

1. If \(P_i < \max(P_1,P_2,\ldots,P_{i-1})\)

\(\displaystyle d[i][P_i]=\max\left(d[i-1][P_i],\max_{1\le j < P_i}d[i-1][j]+1\right)\). Also, for \(p\neq P_i\), we have \(d[i][p]=d[i-1][p]\).

2. If \(P_i > \max(P_1,P_2,\ldots,P_{i-1})\)

Either \(x\) and \(y\) always becomes \(P_i\). Since it is better to have smaller \(\min(x,y)\), we always choose the larger and set it to \(P_i\). Therefore, \(d[i][p]=d[i-1][p]+1\).

These transitions can be processed in-place by maintaining them on a segment tree. The complexity is \(O(N\log N)\).

In fact, a further observation suggests the following fact. Let \(Q\) be the sequence obtained by removing all elements with \(P_i>\max(P_1,P_2,\ldots, P_{i-1})\) from \(P\). Then the answer is the number of remove elements, plus the length of a LIS (Longest Increasing Subsequence) of \(Q\). Finding a LIS and applying this fact is also accepted.

Sample code (Python 3)

import sys
from atcoder.segtree import SegTree

input = sys.stdin.readline
INF = 10**9
n = int(input())
a = list(map(int, input().split()))
seg = SegTree(max, -INF, n + 1)
seg.set(0, 0)
ma = 0
ans = 0
for v in a:
    if ma < v:
        ans += 1
        ma = v
    else:
        seg.set(v, max(seg.get(v), seg.prod(0, v) + 1))
print(ans + seg.all_prod())

Sample code (Python3)

import bisect


def lis(seq):
    if len(seq) == 0:
        return 0
    LIS = [seq[0]]
    for i in range(len(seq)):
        if seq[i] > LIS[-1]:
            LIS.append(seq[i])
        else:
            LIS[bisect.bisect_left(LIS, seq[i])] = seq[i]
    return len(LIS)


n = int(input())
p = list(map(int, input().split()))
q = []
ans = 0
max_val = -1
for v in p:
    if max_val < v:
        max_val = v
        ans += 1
    else:
        q.append(v)
print(ans + lis(q))