Problem : https://practice.geeksforgeeks.org/problems/save-gotham/0

save-gotham.cpp

/*
	Problem:- Save Gotham!
	Link:- https://practice.geeksforgeeks.org/problems/save-gotham/0
	Author:- Mishal Shah
*/
#include "bits/stdc++.h"
#define MOD 1000000001
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int i,j,n;
		long long sum=0;
		cin>>n;
		int a[n];
		stack<int> b;
		for(i=0;i<n;i++)
		{
			cin>>a[i];
		}
		for(i=0;i<n;i++)
		{
			if(i==0)
			{
				b.push(a[i]);
			}
			else
			{
				if(a[i]>b.top())
				{
					while(!b.empty() && a[i]>b.top())
					{
						//cout<<sum<<" ";
						sum = (sum%MOD + a[i]%MOD)%MOD;
						b.pop();
					}
				}
				b.push(a[i]);
			}
		}
		cout<<sum<<endl;		
	}
}