The operation defined in the problem statement shares a lot with that of problem C. Following problem C, let us regard it as a right cyclic shift on a segment. An observation similar to problem C suggests the following:

• Let \(B\) be a sequence obtained by applying an operation on segment \([l,r]\). Let \(m\) and \(M\) be the smallest and largest \(i\) such that \(A _ i\ne B _ i\). Then such \(m\) and \(M\) either do not exist (i.e. \(A=B\)), or performing an appropriate operation on \([m,M]\) yields \(B\).

Therefore, counting the cases where the operation is performed on \([l,r]\) to make \(A _ l\ne B _ l\) and \(A _ r\ne B _ r\), and finally adding the \(A=B\) case to the count, yields the correct answer. Let us say an operation is minimal if the former condition is satisfied.

When a right cyclic shift is performed, \(B _ l=A _ r\) and \(B _ r=A _ {r-1}\). Therefore, the operation on a segment \([l,r]\) is minimal if and only if \(A _ l\ne A _ r\) and \(A _ r\ne A _ {r-1}\).

Since the operation is minimal, operations for different \([l,r]\) yield different sequences. Hence, it suffices to count the pairs \((l,r)\) satisfying the conditions above.

For a fixed \(r\), consider how many \(l\) satisfies the conditions. The count is \(0\) if \(A _ r=A _ {r-1}\), and equals the number of indices \(l\ (l\lt r)\) such that \(A _ l\ne A _ r\) otherwise. The latter count can be obtained by scanning in increasing order of \(r\) and managing the number of occurrences of each value.

Hence, the problem can be solved in a total of \(O(N)\) time.

The following is sample code.

#include <iostream>
#include <vector>

int main() {
    using namespace std;
    unsigned N;
    cin >> N;
    vector<unsigned> A(N);
    for (auto&& a : A) {
        cin >> a;
        --a;
    }
    
    vector<unsigned> cnt(N);
    unsigned long ans{1};
    for (unsigned i{}; i < N; ++i) {
        if (i && A[i] != A[i - 1])
            ans += i - cnt[A[i]];
        ++cnt[A[i]];
    }

    cout << ans << endl;
    return 0;
}