自制阳寿测试器

#include<bits/stdc++.h>
using namespace std;

const int N = 1e7 + 10;
int n;
int w[N];
int stk[N], ls[N], rs[N];

void build()
{
	int top = 0, pos = 0;
	for(int i = 1; i <= n; i ++)
	{
		pos = top;
		while(pos > 0 && w[stk[pos]] > w[i]) pos --;
		if(pos > 0) rs[stk[pos]] = i;
		if(pos < top) ls[i] = stk[pos + 1];
		stk[++ pos] = i;
		top = pos;
	}
} 
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++) scanf("%d", &w[i]);
	build();
	long long ans1 = 0, ans2 = 0;
	for(int i = 1; i <= n; i ++)
	{
		ans1 ^= 1ll * i * (ls[i] + 1);
		ans2 ^= 1ll * i * (rs[i] + 1);
	}
	printf("%lld %lld\n", ans1, ans2);
	
	return 0;
}