要約：\(\sum_x f(x)\) の形の式は \(\sum_k k*|\{x \mid f(x)=k\}|\) と変形すると簡単に求められることがあります。

index は \(0\) からとします。

ペア \((i,j)\) を固定するごとに、\((A_i,A_j)\) に対する操作が答えに何度寄与するかを考えます。

ペア \((i,j)\) の寄与回数は、\(A_i=A_j\) のとき \(0\)、そうでないとき \(\min(i+1,N-j)\) です。これを \(f(i,j)\) とします。求めるものは \(\sum_{(i,j)}f(i,j)\) です。これを冒頭で述べたとおり、\(f(i,j)\) の値ごとに分けて求めることを考えます。

• \(\min(i+1,N-j)=1\) である組、つまり \(i=0\) または \(j=N-1\) であるような \((i,j)\) について考えます。
  • \((0,*)\) の寄与回数の合計は、\(A_0\neq A_j\) を満たす \(0\leq j < N\) の個数の \(1\) 倍です。
    
  • \((*,N-1)\) の寄与回数の合計は、\(A_i \neq A_{N-1}\) を満たす \(0 \leq i <N\) の個数の \(1\) 倍です。
    
  • もし \(A_0 \neq A_{N-1}\) であれば、その分を重複して数えているため \(1\) を引きます。
• \(\min(i+1,N-j)=2\) である組、つまり「\(i=1\) かつ \(j < N-1\)」または「\(i\geq 1\) かつ \(j=N-2\)」であるような \((i,j)\) について考えます。
  • \((1,*)\) の寄与回数の合計は、\(A_1\neq A_j\) を満たす \(1\leq j < N-1\) の個数の \(2\) 倍です。
    
  • \((*,N-2)\) の寄与回数の合計は、\(A_i \neq A_{N-2}\) を満たす \(1 \leq i <N-1\) の個数の \(2\) 倍です。
    
  • もし \(A_1 \neq A_{N-2}\) であれば、その分を重複して数えているため \(2\) を引きます。
• 以下同様

これは \(\min(i+1,N-j)\) の小さい順に求めることで以下のように実装できます

実装例 (Python)

N=int(input())
A=list(map(int,input().split()))
C=[0]*(N+1)
for x in A: C[x]+=1

ans=0
for i in range((N+1)//2):
  L=A[i]
  R=A[~i]  # 後ろから i 番目
  ans+=(N-2*i-C[L])*(i+1)
  ans+=(N-2*i-C[R])*(i+1)
  if L!=R: ans-=i+1
  C[L]-=1
  C[R]-=1

print(ans)