We can observe that a pair $(a_{x_2}, b_{y_2})$ can be matched with a preceding pair $(a_{x_1}, b_{y_1})$ only if the following necessary conditions are met:$$x_1 < x_2$$$$y_1 < y_2$$This structure inherently mirrors the properties of the Longest Common Subsequence (LCS). Consequently, instead of tracking index constraints explicitly, we can focus solely on the values of the pairs, allowing us to reduce the problem's dimensionality.

Dynamic Programming State DefinitionLet:

• $\text{dp}[0][i]$ be the maximum length of a valid subsequence ending with the value $b[i]$, such that the sequence is strictly decreasing at this step ($b[i] < b[\text{pre}]$, where $\text{pre}$ is the index immediately preceding $i$ in our target subsequence).

• $\text{dp}[1][i]$ be the maximum length of a valid subsequence ending with the value $b[i]$, such that the sequence is strictly increasing at this step ($b[i] > b[\text{pre}]$).

State TransitionsBy fixing $a[i]$ and iterating through all possible elements $b[j]$, we can maintain the two longest oscillating subsequences using the following transitions:$$\text{dp}[0][j] = \max(\{\text{dp}[1][t] + 1 \mid b[t] > b[j]\})$$$$\text{dp}[1][j] = \max({\text{dp}[0][t] + 1 \mid b[t] < b[j]})$$

Note on Base Cases: Any commong subsequence with a length of less than 3 is vacuously valid, as the alternating condition requires at least 3 elements to be tested. Therefore, for lengths shorter than 3, the problem simply reduces to finding a standard LCS between arrays $a$ and $b$ of length less than 2.

#define For(i, a, b) for (int i = (a); i <= (b); i++) 
#define tcT template <class T
tcT> bool minimize(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
tcT> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

void solve() {
    int n; cin >> n;
    int a[n + 1]; For (i, 1, n) cin >> a[i];

    int m; cin >> m;
    int b[m + 1]; For (i, 1, m) cin >> b[i];

    vector<vector<int>> dp(2, vector<int>(m + 1, 0));

    For (i, 1, n) {
        int curLen0 = 0, curLen1 = 0;
        For (j, 1, m) {
            if (a[i] == b[j]) {
                maximize(dp[0][j], curLen0 + 1);
                maximize(dp[1][j], curLen1 + 1);
            }
            if (a[i] < b[j]) maximize(curLen0, dp[1][j]);
            if (a[i] > b[j]) maximize(curLen1, dp[0][j]);
        }
    }    

    int ans = 0;
    For (i, 1, m) maximize(ans, max(dp[0][i], dp[1][i]));

    dp.assign(n + 5, vector<int>(m + 1, 0));

    For (i, 1, n) {
        For (j, 1, m) {
            if (a[i] == b[j]) maximize(dp[i][j], dp[i - 1][j - 1] + 1);
            else {
                maximize(dp[i][j], dp[i - 1][j]);
                maximize(dp[i][j], dp[i][j - 1]);
            }
        }
    }

    maximize(ans, min(2, dp[n][m]));

    cout << ans << endl;
}