The problem can be rephrased using the mod-\(K\) prefix sums \(S\) of \(A\), defined as \(\displaystyle S _ i=\sum _ {j=1} ^ iA _ i\pmod K\):

Define the score of an integer sequence by the number of adjacent terms with the same value. Among the subsequences of a length-\(N\) sequence \(S=(S _ 0,S _ 1,\ldots,S _ N)\), find the maximum score of one containing \(S _ 0\) and \(S _ N\).

The score does not become larger by removing \(S _ 0\) or \(S _ N\), so we may find the maximum score among all subsequences.

For a score-\(k\) subsequence of \(S\), let \((S _ {l _ i},S _ {r _ i}) _ {i=1,2,\ldots,k}\) be the pairs of adjacent terms with the same value. Then the right half-open intervals \(\lbrack l _ i,r _ i\rparen\) are pairwise disjoint. Conversely, if we can choose pairwise disjoint \(k\) right half-open intervals \(\lbrack l,r\rparen\) with \(S _ l=S _ r\), then we can obtain a subsequence of score \(k\) by picking their endpoints.

Therefore, the problem is further transformed as follows:

For an integer sequence \(S\), define the set of intervals \(I\coloneqq\lbrace\lbrack l,r\rparen\mid S _ l=S _ r\rbrace\). Find the maximum size of a subset of \(I\) where the intervals are pairwise disjoint.

This is known as interval scheduling problem, which can be solved with a greedy algorithm. On its own, the size of \(I\) might be as large as \(\Theta(N ^ 2)\), but by taking the leftmost possible \(S _ r\) for each \(S _ l\), the number of intervals can be reduced to \(O(N)\) without changing the answer (because, for \(l,m\), and \(r\) with \(S _ l=S _ m=S _ r\ (l\lt m\lt r)\), if one can choose \(\lbrack l,r\rparen\), then it is better to choose two intervals \(\lbrack l,m\rparen\) と \(\lbrack m,r\rparen\)).

The following is the sample code.

#include <iostream>
#include <map>

int main() {
    using namespace std;
    unsigned N, K;
    cin >> N >> K;
    
    unsigned ans{};

    // Associate array from the value of S to its position
    map<unsigned, unsigned> prev;
    prev[0] = 0;
    for (unsigned S{}, last{}; const auto &[i, A] : views::istream<unsigned>(cin) | views::enumerate) {
        (S += A) %= K; // Find the prefix sum
        // If the prefix sum has already appeared in the past, and does not overlap with any chosen interval
        if (prev.contains(S) && last <= prev[now]) {
            ++ans;
            last = i + 1; // Choose that interval
        }
        prev[S] = i + 1; // Update the position
    }
    
    cout << ans << endl;
    return 0;
}