まず、ある連続部分列 \(B\) について \(f(B)\) の値を求めるにはどうすればよいか考えましょう。

\(A=(2,4,4,9,4,8,9,7,4)\) とすると、

• \([1,4]\) 要素目からなる部分列 \((2,4,4,9)\) について

  • \(1\) 要素目と \(4\) 要素目は異なるので、片方を変更する必要がある。
  • \(2\) 要素目と \(3\) 要素目は同じなので、変更する必要はない。

• 以上より、 \(f(2,4,4,9)=1\) である。

• \([5,9]\) 要素目からなる部分列 \((4,8,9,7,4)\) について

  • \(5\) 要素目と \(9\) 要素目は同じなので、変更する必要はない。
  • \(6\) 要素目と \(8\) 要素目は異なるので、片方を変更する必要がある。

• 以上より、 \(f(4,8,9,7,4)=1\) である。

下図のように、「回文にしたい時に等しくするべき要素」を線で結ぶようなイメージを持つとよいでしょう。

• 線で結ばれた要素が等しいなら答えは変わりません。以降はこれを「良い線」と呼びます。
• 線で結ばれた要素が異なるなら答えは増加します。以降はこれを「悪い線」と呼びます。
• 以降はこの \(2\) つを総称して「線」と呼びます。

数えるべきは全ての連続部分列についての悪い線の合計です。
さらに、 (悪い線の合計) = ( 線の合計 - 良い線の合計 ) と書けます。
悪い線の合計を直接求めるのは厳しそうなので、等号の右辺を求める方針で進めていきます。

まず、線の合計を求めにかかります。これは以下の式で求めることができます:
\(\displaystyle \sum_{i=1}^{N} \left ( (N+1-i) \times \left \lfloor \frac{i}{2} \right \rfloor \right )\) ( 但し \(\lfloor x \rfloor\) は床関数、即ち \(x\) の小数点以下を切り捨てた値)
うまく式変形して \(O(1)\) で求めても良いですし、この式を愚直に計算して \(O(N)\) で求めても良いです。コンテスト本番ではより速く実装できる方法を優先すべきでしょう。

では、良い線の合計はどう数えればよいでしょうか?
ここで、「主客転倒」 (うまく足し方を取り換えて数え上げるテク) を使います。
「全ての連続部分列について良い線がいくつあるかを足し合わせる」 → 「ある良い線が何個の連続部分列で数えられるかを、全ての良い線について足し合わせる」と足し方を取り換えます。
例えば \(A=(2,4,4,9,4,8,9,7,4)\) について、 \(3\) 要素目と \(5\) 要素目を結ぶ良い線は \([1,7],[2,6],[3,5]\) 要素目の連続部分列にて数えられます。(下図参照)

より一般には、 \(l\) 要素目と \(r\) 要素目を結ぶ良い線は \(\min(l,N+1-r)\) 個の連続部分列について数えられることが分かります。
いよいよ、問題は以下のものに帰着されます。

• 整数 \(x\) について、 \(x\) がある位置を昇順に並べたものを \(P\) とする。 ( 例えば \(A=(2,4,4,9,4,8,9,7,4), x=4\) のとき \(P=(2,3,5,9)\) となります)
• 求めたい値は \(\displaystyle \sum_{i=1}^{|P|-1} \sum_{j=i+1}^{|P|} \min(P_i,N+1-P_j)\) を全ての \(x\) について足し合わせたものである。

この問題は以下の手順で解くことができます。

• 最初、 \(l=1,r=|P|\) とする。
• 上記の手順を \(l<r\) である限り繰り返す。
  • もし \(P_l < N+1-P_r\) であれば、 \((x,y)=(l,l+1),(l,l+2),\dots,(l,r)\) について \(P_x < N+1-P_y\) なので、答えに \((r-l) \times P_l\) を加算して \(l=l+1\) とする。
  • そうでなければ、 \((x,y)=(l,r),(l+1,r),\dots,(r-1,r)\) について \(P_x \ge N+1-P_y\) なので、答えに \((r-l) \times (N+1-P_r)\) を加算して \(r=r-1\) とする。

以上より、良い線の合計も求めることができたので、この問題を解くことができました。
バケットソートの要領で \(P\) を入力を順に受け取りながら (全ての \(x\) について) 予め構成していくことで、時間計算量 \(O(N)\) で実装できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  long long n;
  cin >> n;
  vector<vector<long long>> p(n+1);
  for(int i=1;i<=n;i++){
    long long x;
    cin >> x;
    p[x].push_back(i);
  }
  long long res=0;
  for(long long i=1;i<=n;i++){
    res+=(n+1-i)*(i/2);
  }
  for(long long i=1;i<=n;i++){
    long long l=0,r=p[i].size()-1;
    while(l<r){
      if(p[i][l]<(n+1-p[i][r])){
        res-=(r-l)*p[i][l];
        l++;
      }
      else{
        res-=(r-l)*(n+1-p[i][r]);
        r--;
      }
    }
  }
  cout << res << "\n";
  return 0;
}