int countSubSeqs(vector<int> &A) {
    int N = A.size();
    if (N == 0) {
        return 1;
    }
    vector<int> ans(N, 0);
    unordered_map<int, int> last;
    ans[0] = 2;
    last[A[0]] = 0;
    for (int i = 1; i < N; i++) {
        if (last.find(A[i]) == last.end()) {
            ans[i] = 2 * ans[i - 1];
        } else {
            int extra = last[A[i]] == 0 ? 1 : ans[last[A[i]] - 1];
            ans[i] = 2 * ans[i - 1] - extra;
        }
        last[A[i]] = i;
    }
    return ans[N - 1];
}