T5

我们可以发现，最终的答案为假设全要修改的，减去序列内不要给的

而假设全要修改的值为

$$\sum_{i=1}^n (n-i+1)\times \lfloor\frac{i}{2}\rfloor$$

而对于不用修改的部分，我们可以把每种数的位置催在一个集合里，然后用双指针去找两两对称，每个位置的贡献是

$$min(p_j,n-p_j+1)\times p_{i,j}$$

且这部分可以用双指针实现，再把这两个数相减就行了

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,cnt,ans;
int a[200010];
vector<int>b[200010];
signed main() {
	freopen("E.in","r",stdin);
	freopen("E.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		cnt+=(n-i+1)*(i/2);
		b[a[i]].push_back(i);
	}
	for(int i=1;i<= n;i++){
		int l=0,r=b[i].size()-1;
		while (l<r){
			if(b[i][l]<n-b[i][r]+1) {
				ans+=(r-l)*b[i][l];
				l++;
			} else {
				ans+=(r-l)*(n-b[i][r]+1);
				r--;
			}
		}
	}
	
	cout << cnt - ans;
	return 0;
}