Before going down, if you do not have any idea of the intuitions of the solution, then read the upto and including Important observation section of this blog. If you understood the intuition behind the approach, we can now proceed.

While calculating the $$$nextGreater(i)$$$ for each $$$i$$$, we can calculate it's contribution. Then we look at the queries where $$$l=i$$$. Now, we can do a binary search on the stack to find the maximum element's index within $$$r$$$. Then we can add the sub-ranges contribution and subtract the range-sum of $$$[l,r]$$$. Let's say the maximum element's index before $$$r$$$ is $$$m$$$. So, the answer for the query will be $$$contribution([l,n])-contribution([m,n])+contribution([m, r])-\sum_{i=j}^ra_i$$$.

This way, the complexity of this solution is $$$O((n+q)\log n)$$$. And it uses no data structures. Here is my submission