i tried to implement the O(n) solution but couldn’t , here is the editorial https://discuss.codechef.com/problems/SUBMIN
I tried to implement the O(n) solution but wasn’t able to , here is the code and link .
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <list>
typedef long long int ll;
using namespace std;
ll a[1000000+100],b[1000000+100]={0};
int main() {
// your code goes here
ll n;
cin>>n;
for(ll i=0;i<n;i++)cin>>a[i];
list<ll> k1,k2;
for(ll i=0,j=n-1;i<n;i++,j--)
{
ll k11,k22;
while(!k1.empty()&&a[k1.back()]>a[i])
k1.pop_back();
while(!k2.empty()&&a[k2.back()]>a[j])
k2.pop_back();
if(k1.empty())k11=0;
else k11 = 1+k1.back();
if(k2.empty())k22=n-1;
else k22 = k2.back()+1;
b[a[i]] += (i-k11+1)*(k22-i+1);
k1.push_back(i);
k2.push_back(i);
}
ll q;
cin>>q;
while(q--)
{
ll temp;
cin>>temp;
cout<<b[temp]<<endl;
}
return 0;
}