\(L<R\)を満たす\((L,R)\)について、\(f(L,R)\)を\(f(L,R-1)\)との差分で表すことを考えます。すると、

\(\begin{aligned}f(L,R)=\begin{cases}f(L,R-1)-1&(A_{L},\ldots,A_{R-1}にA_R-1とA_R+1がともに含まれ、かつA_Rは含まれない)\\f(L,R-1)+1&(A_L,\ldots,A_{R-1}にA_R-1,A_R,A_R+1がどれも含まれない)\\f(L,R-1)&(それ以外)\end{cases}\end{aligned}\)

となります。

「\(A_{L},\ldots,A_{R-1}\)に\(A_R-1\)と\(A_R+1\)がともに含まれ、かつ\(A_R\)は含まれない」ような\(L(1\leq L<R)\)の個数を\(g_1(R)\)、「\(A_L,\ldots,A_{R-1}\)に\(A_R-1,A_R,A_R+1\)がどれも含まれない」ような\(L(1\leq L<R)\)の個数を\(g_2(R)\)とし、また\(h(R):=\sum_{L=1}^{R}f(L,R)\)とします。すると、先の式より、

\(h(R)=\begin{aligned}\sum_{L=1}^{R-1}f(L,R)+f(R,R)=h(R-1)-g_1(R)+g_2(R)+1\end{aligned}\)

が成り立ちます。 求める答えは\(\sum_{R=1}^N h(R)\)なので、各\(R\)に対して\(g_1(R),g_2(R)\)の値が求められればよいです。

ここで、\(P_R(a)\)を、「\(L<R\)かつ\(A_L=a\)を満たす最大の\(L\)（存在しない場合は\(0\)とする）」として定めます。すると、

\(\begin{aligned}g_1(R)=\max\{\min\{P_R(A_R-1),P_R(A_R+1)\}-P_R(A_R),0\}\end{aligned}\\g_2(R)=R-1-\max\{P_R(A_R-1),P_R(A_R),P_R(A_R+1)\}\)

が成り立ちます。\(P_R\)はin-placeに更新できるため、\(R=1,2,\ldots,N\)の順に\(g_1(R),g_2(R),h(R)\)を求めていけば、時間計算量\(O(N)\)でこの問題を解くことができます。

実装例（Python）