Let \(L_i\) be the count of distinct elements in \((A_1,A_2,\ldots,A_i)\), and

\(R_i\) be the count of distinct elements in \((A_i,A_{i+1},\ldots,A_N)\).

Then the answer is \(\max_{1 \leq i \leq N-1} (L_i+R_{i+1})\). In other words, once we evaluate \(L\) and \(R\), we can find the answer too.

By reversing \(A\), one can find \(R\) in the same manner as finding \(L\); and \(L\) can be indeed found fast as follows:

Let \(S=0\) and \(V=(0,0,0,0,\ldots,0) \), where \(V\) is a length-\(N\) array.

For each \(i=1,2,\ldots,N\) in order:

• if \(V_{A_i}=0\), then let \(V_{A_i} \larr 1\) and \(S \larr S+1\).
• \(L_i \larr S\).

\(R\) can be found in the similar way. All that left is to evaluate the aforementioned expression to find the answer.

The time complexity is \(O(N)\).

Sample code (C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &e : a)
        cin >> e;
    vector<int> suml(n), sumr(n);
    vector<int> vis(n + 1, 0);
    int now = 0;
    for (int i = 0; i < n; ++i) {
        if (!vis[a[i]]) {
            now++;
        }
        vis[a[i]] = 1;
        suml[i] = now;
    }
    now = 0;
    vis = vector<int>(n + 1, 0);
    for (int i = n - 1; i >= 0; --i) {
        if (!vis[a[i]]) {
            now++;
        }
        vis[a[i]] = 1;
        sumr[i] = now;
    }
    int ans = 0;
    for (int i = 0; i < n - 1; ++i) {
        ans = max(ans, suml[i] + sumr[i + 1]);
    }
    cout << ans << endl;
}