# HackerEarth Harmonic Triplets problem solution

In this HackerEarth Harmoni Triplets problem solution, you are given an array A. A triplet is said to be a Harmonic triplet if it satisfies the following conditions :
1. i < j < k
2. A[i] <= A[j] >= A[k]

You have to find the harmonic triplet with the maximum value of A[i] x A[j] x A[k]. You are given q queries, wherein each query you are given jth index and you have to find the harmonic triplet with value at jth index which has a maximum product.

## HackerEarth Harmonic Triplets problem solution.

`#include <bits/stdc++.h>using namespace std;#define mp make_pair#define pb push_backtypedef long long ll;typedef long double ld;typedef pair<int,int> pp;typedef pair<pp,pp> ppi;typedef vector<int> vv;int st[5000005];int a[1000005];ll ans[1000005];ll build(int s,int e,int i){    if(s==e)    {        st[i]=a[s];        return st[i];    }    int mid=(s+e)/2;    st[i]=max(build(s,mid,2*i+1),build(mid+1,e,2*i+2));    return st[i];}ll query(int s, int e,int l,int r,int i){    if(l<=s && r>=e)        return st[i];    if(e<l || s>r)        return 0;    int mid=(s+e)/2;    return max(query(s,mid,l,r,2*i+1),query(mid+1,e,l,r,2*i+2));}void update(int s,int e,int val,int idx,int i){    if(idx<s || idx>e)        return;        st[i]=max(st[i],val);    if(s!=e)    {        int mid=(s+e)/2;        update(s,mid,val,idx,2*i+1);        update(mid+1,e,val,idx,2*i+2);        st[i]=max(st[2*i+1],st[2*i+2]);    }}int main() {    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);    int t;    scanf("%d",&t);        while(t--)    {        memset(a,0,sizeof(a));        memset(ans,0,sizeof(ans));        memset(st,0,sizeof(st));                int n,q;        scanf("%d %d",&n,&q);                for(int i=0;i<n;i++)            scanf("%d",&a[i]),ans[i]=1;                for(int i=0;i<n;i++)        {            ans[i]=query(0,1000000,0,a[i],0)*a[i];            update(0,1000000,a[i],a[i],0);        }                memset(st,0,sizeof(st));        for(int i=n-1;i>=0;i--)        {            ans[i]*=query(0,1000000,0,a[i],0);            update(0,1000000,a[i],a[i],0);        }                while(q--)        {            int j;            scanf("%d",&j);            printf("%lld\n",ans[j-1]);        }    }    return 0;}`

### Second solution

`#include<bits/stdc++.h>#define ll long longusing namespace std;int n,q;ll a[1000005],ans[1000005];set<ll>s;set<ll> :: iterator it;void calc(ll temp,int i){    it=s.lower_bound(temp);        if(it==s.begin())        {            if(*it == temp)ans[i]*=(*it);                else ans[i]=0;        }        else if(it==s.end())        {                it--;                ans[i]*=(*it);        }        else        {                if(*it == temp)ans[i]*=(*it);                else                {                  it--;                      ans[i]*=(*it);                }        }        s.insert(temp);}int main(){    int t;ios::sync_with_stdio(0);cin.tie(0);    cin>>t;    while(t--)    {        cin>>n>>q;        s.clear();        ans[0]=ans[n-1]=0;        cin>>a[0];s.insert(a[0]);        for(int i=1;i<n;i++)        {            cin>>a[i];            ans[i]=a[i];        }        for(int i=1;i<n;i++)        {            calc(a[i],i);        }        s.clear();        s.insert(a[n-1]);ans[n-1]=0;        for(int i=n-2;i>=0;i--)        {            calc(a[i],i);        }        while(q--)        {            int j;            cin>>j;            cout<<ans[j-1]<<"\n";        }    }    return 0;}`