I observed a interesting observation in D let $$$m = (2^k)+1$$$ The frequency value $$$A_1$$$ and $$$A_n$$$ and $$$Xor(A_1,A_n)$$$ will be $$$Ceil(m/3)$$$, $$$Ceil(m/3)$$$, $$$floor(m/3)$$$. so by this observation you can do it in $$$O(n)$$$ time complexity

In F I used difference array to track the sum of all position which contains height x, and after it I check how many blocks finally will be in right side, we can easily find their positional sum. and the answer without removing any block will be sum of all height's answer which is their final positional sum — initial sum.

void solve() {
	ll n;
	cin >> n;
	vector<ll>a(n);
	for (auto &it : a)cin >> it;

	vector<ll>b(n + 2);
	ordered_set st;
	for (int i = 0; i < n; i++) {
		b[1] += i + 1;
		st.insert(a[i]);
		b[a[i] + 1] -= i + 1;
	}

	for (int i = 1; i <= n + 1; i++) {
		b[i] += b[i - 1];
	}
	vector<ll>c(n, 1e8);
	ll mn = 1e8;
	for (int i = n - 1; i >= 0; i--) {
		mn = min(mn, a[i]);
		c[i] = mn;
	}

	ll sum = 0;
	for (int i = 1; i <= n; i++) {
		ll t = st.order_of_key(i - 1);

		ll tot = n * (n + 1) / 2;

		ll r = n - t;

		ll prev_sum = r * (r + 1) / 2;

		sum += tot - prev_sum - b[i];

	}

	ll mx = sum;

	for (int i = n - 1; i >= 0; i--) {
		ll t = st.order_of_key(a[i] - 1);

		mx = max(mx, sum + t - (n - i));

	}

	cout << mx << endl;

}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

This is a wonderful tool, although it needs lot of improvement, we will do gradually.