黒板にいくつかの整数が書かれている場合に、操作回数を最小とするために \(l,r\) は \(r-l\) が極大になるように選べば良いです。つまり、

• \(l-1\) は黒板に書かれていない。
• \(l\) 以上 \(r\) 以下の整数はどれも黒板に書かれている。
• \(r+1\) は黒板に書かれていない。

これらの \(3\) つの条件を満たす \((l,r)\) を選び、順番に黒板から消していけば良いです。

この事実を踏まえて問題を解いていきます。

整数 \(1\le c\le N\) を固定し、\(f(L,R)\) の計算過程で \(l=c\) とする操作が現れるような整数の組 \((L,R)\) の個数を \(g(c)\) とします。すると、求める答えは \(\displaystyle \sum_{c=1}^Ng(c)\) と一致することが分かります。以降は各 \(c\) に対し \(g(c)\) を求めることを考えます。

\(l=c\) とする操作をする条件は、上の考察により \(S=\{A_L,A_{L+1},\ldots,A_R\}\) に対し以下の \(2\) つを共に満たすことであることが分かります。

• \(c-1\notin S\)
• \(c\in S\)

よって、 \(g(c)\) は \(c-1\notin S\) を満たす \((L,R)\) の組の個数から \(c-1\notin S\) かつ \(c\notin S\) を満たす \((L,R)\) の組の個数を引いた値と一致します。

ここで、 \(G_c\) を \(A_i=c\) を満たす \(i\) の集合とすると、 \(c\notin S\) は \(L\) 以上 \(R\) 以下の整数が全て \(G_c\) に属さないことと同値です。この条件を満たす \((L,R)\) の組は \(G_c=\{X_1,X_2,\ldots,X_{|G_c|}\}\) \((X_1<X_2<\ldots<X_{|G_c|}),\) \(X_0=0,\) \(X_{|G_c|+1}=N+1\) として \(\displaystyle \sum_{k=0}^{|G_c|}\frac{(X_{k+1}-X_k)(X_{k+1}-X_k-1)}2\) 通りです。 \(c-1\notin S\) かつ \(c\notin S\) を満たす \((L,R)\) の組の個数も同様にして求めることができます。

これらの計算をすることで各 \(c\) に対する \(g(c)\) の値が求まるので、それらの総和を計算することで答えを求めることができます。計算量は \(O(N)\) です。

なお、以下では可視性を上げるために \(O(N\log N)\) 時間の実装を載せています。

実装例(Python3)

n = int(input())
a = list(map(int, input().split()))
g = [[] for i in range(n + 1)]
for i in range(n):
    g[a[i] - 1].append(i)

def f(x):
    res = 0
    for i in range(1, len(x)):
        c = x[i] - x[i - 1]
        res += c * (c - 1) // 2
    return res

ans = 0
for i in range(1, n + 1):
    ans += f([-1] + g[i] + [n])
    ans -= f([-1] + sorted(g[i - 1] + g[i]) + [n])
print(ans)