この問題中で定義されている操作は、C 問題で定義されている操作と多くの部分が共通しています。 C 問題と同様に、区間に対して右に巡回シフトを行う操作だと思うことにしましょう。 C 問題の考察と同様にして、以下のような事実がわかります。

• 区間 \([l,r]\) に対して操作を行って得られる列を \(B\) とする。\(A _ i\ne B _ i\) となる最小の \(i\) を \(m\) 、最大の \(i\) を \(M\) とすると、そのような \(m,M\) は存在しない（\(A=B\) である）か、\(A\) で区間 \([m,M]\) に対して適切な操作を行うことで \(B\) が得られる。

よって、区間 \([l,r]\) に対して操作を行った結果 \(A _ l\ne B _ l\) かつ \(A _ r\ne B _ r\) となるような操作のみを考えて数え上げ、最後に \(A=B\) となる場合を加えることにしても答えは変わりません。 前者の条件を満たす操作を極小な操作と呼ぶことにします。

右に巡回シフトを行ったとき、\(B _ l=A _ r\) かつ \(B _ r=A _ {r-1}\) です。 よって、区間 \([l,r]\) に対する操作が極小である条件は、\(A _ l\ne A _ r\) かつ \(A _ r\ne A _ {r-1}\) と同値です。

操作が極小であることから、異なる \([l,r]\) に対して得られる列は異なります。 よって、上の条件を満たす組 \((l,r)\) を数え上げればよいです。

\(r\) を固定して対応する \(l\) がいくつあるか考えてみましょう。 これは、\(A _ r=A _ {r-1}\) なら \(0\) 個、そうでなければ \(A _ l\ne A _ r\) であるような \(l\ (l\lt r)\) の個数です。 後者の値は、\(r\) の昇順に処理してそれぞれの値が出現した回数を管理することで計算できます。

以上より、全体で \(O(N)\) 時間で答えを求めることができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>

int main() {
    using namespace std;
    unsigned N;
    cin >> N;
    vector<unsigned> A(N);
    for (auto&& a : A) {
        cin >> a;
        --a;
    }
    
    // cnt[i] := これまでに i が何度出現したか
    vector<unsigned> cnt(N);
    unsigned long ans{1};
    for (unsigned i{}; i < N; ++i) {
        if (i && A[i] != A[i - 1]) // A[i] != A[i - 1] のとき、A[i] != A[j] であるような j の個数を足す
            ans += i - cnt[A[i]]; // j 全体から A[i] = A[j] であるような j の個数を引く
        ++cnt[A[i]];
    }

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