答えは、\(1\) が含まれる連続部分列の個数 \(+\) \(2\) が含まれる連続部分列の個数 \(+\ldots+\) \(N\) が含まれる連続部分列の個数です。

以下では、\(i\) が含まれる連続部分列の個数を \(\mathrm{O}(C_i)\) ( ここで \(C_i\) は \(A\) に含まれる \(i\) の個数) で求める方法を説明します。これができれば、全体の計算量は \(\mathrm{O}(N)\) となります。

数え上げで良く使われるテクニックとして、余事象を考えるものがあります。今回も、\(i\) が含まれない連続部分列の個数を求め、全体から引きましょう。

簡単のため、\(A\) の両端に \(i\) を追加することにします。（こうしても答えは変わりません）

このとき、\(A_x = i\) なるインデックス \(x\) を昇順に並べると、\(x=(x_0=0,x_1,\ldots,x_{C_i+1} = N+1)\) となります。 ここで、\(i\) が含まれない連続部分列の個数は、

（左端が\(x_0+1\) 以上、右端が \(x_1-1\) 以下の連続部分列の個数)

\(+\) （左端が\(x_1+1\) 以上、右端が \(x_2-1\) 以下の連続部分列の個数)

\(\ldots +\) (左端が\(x_{C_i}+1\) 以上、右端が \(x_{C_i+1}-1\) 以下の連続部分列の個数)

となるので、それぞれ計算することで \(\mathrm{O}(C_i)\) で求めることができます。よってこの問題を解くことが出来ました。