# SEDMAX - Editorial

**URL:** <https://discuss.codechef.com/t/sedmax-editorial/86099>\
**Category:** editorial\
**Tags:** easy-medium, editorial, stack, ltime93\
**Created:** [February 26, 2021, 11:55am UTC](https://discuss.codechef.com/t/sedmax-editorial/86099 "2021-02-26T11:55:32Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![cherry0697](https://discuss.codechef.com/user_avatar/discuss.codechef.com/cherry0697/32/348418_2.png) [@cherry0697](https://discuss.codechef.com/u/cherry0697)\
**Post date:** [February 26, 2021, 11:55am UTC](https://discuss.codechef.com/t/sedmax-editorial/86099/1 "2021-02-26T11:55:32Z")

</div>

# PROBLEM LINK:

[Practice](https://www.codechef.com/problems/SEDMAX)  
[Contest: Division 1](https://www.codechef.com/LTIME93A/problems/SEDMAX)  
[Contest: Division 2](https://www.codechef.com/LTIME93B/problems/SEDMAX)  
[Contest: Division 3](https://www.codechef.com/LTIME93C/problems/SEDMAX)

**Author:** [Bhavyesh Desai](https://www.codechef.com/users/bhvdsi)  
**Tester:** [Rahul Dugar](https://www.codechef.com/users/rahuldugar)  
**Editorialist:** [Aman Dwivedi](https://www.codechef.com/users/cherry0697)

# DIFFICULTY:

Easy-Medium

# PREREQUISITES:

Observation, Stack

# PROBLEM:

You are given an array A of length N. Your task is to find out the number of different possible costs that can be obtained across all possible choices for the subarray.

The cost is calculated as follows:

- A subarray B of size at least 2 will be chosen.
- The cost will be calculated as the difference between the maximum and the second maximum element in the subarray B.

# QUICK EXPLANATION:

- An element A\_i can act as a second maximum element for at most two elements of an array, say A\_L and A\_R.

- A\_L is the first greater (or equal) element on the left side of A\_i, whereas A\_R is the first greater (or equal) element on the right side of A\_i in the array.

- Find A\_L and A\_R for every element of an array, which can be done in a single traversal of an array using a stack.

- Find out the difference for every pair of the maximum and second maximum elements.

- Finally, output the number of unique differences possible.

# EXPLANATION:

### Subtask 1:

Here, \sum{N} overall cases is less than or equal to 5 \cdot 10^3

What really matters in the subarray is the maximum and the second maximum element. Suppose we have a subarray [A\_L, A\_{L+1},......, A\_R] and the maximum element be max and the second maximum element is smax.

What happens when a new element A\_{R+1} is added to this subarray?

**Case 1:** A\_{R+1} is greater than than the maximum element max.

- Since A\_{R+1} is the maximum element in the new subarray hence max becomes equal to A\_{R+1}. And the previous max will become smax as now the previous max will be the second maximum element of the new subarray.

**Case 2:** A\_{R+1} is smaller than the maximum element max but greater than the second maximum element smax.

- Now max is still the maximum element in the new subarray hence max will remain as it is. But smax will no longer remain the second maximum element as A\_{R+1} \> smax, hence smax becomes equal to A\_{R+1}.

**Case 2:** A\_{R+1} is smaller than both maximum element max and second maximum element smax.

- In this case, the max and smax will remain as it is as they are still the maximum and the second maximum element of the new subarray respectively.

As every element of an array can be the starting point of the subarray except the last element of the subarray since the minimum length needs to be 2.

Hence taking every element as the starting point of the subarray and keep on adding the elements on this subarray till we reach the rightmost element of the array. Every time we add the element to the subarray, find the maximum and the second maximum element for this new subarray as explained in the cases above. Every time we calculate the difference between the maximum and the second maximum element. Finally, we output the number of unique differences possible.

> **Time Complexity**
>
> O(N^2) per test case

> **Solution**
>
> ```auto
> // Subtask 1
>  
> #include<bits/stdc++.h>
> using namespace std;
>  
> #define int long long
>  
> const int mxN=1e5+5;
> int a[mxN];
> int n;
>  
> int32_t main()
> {
> ios_base::sync_with_stdio(0);
> cin.tie(0);
>  
> int t;
> cin>>t;
>  
> while(t--)
> {
> cin>>n;
>  
> for(int i=1;i<=n;i++)
> {
> cin>>a[i];
> }
>  
> set <int> ans;
>  
> for(int i=1;i<n;i++)
> {
> int ma1=max(a[i],a[i+1]);
> int ma2=min(a[i],a[i+1]);
>  
> ans.insert(ma1-ma2);
>  
> for(int j=i+2;j<=n;j++)
> {
> if(a[j]>ma1)
> {
> ma2=ma1;
> ma1=a[j];
> }
> else if(a[j]>ma2)
> {
> ma2=a[j];
> }
>  
> ans.insert(ma1-ma2);
> }
> }
>  
> cout<<ans.size()<<"\n";
> }
>  
> return 0;
> }
> 
> ```

### Subtask 2:

Since the value of N is large enough, we need to optimize our solution. As the only thing that matters in the problem is to find the pairs (x,y) such that x is the maximum element of the subarray and y is the second maximum element of the subarray. If we can find all the possible pairs then we can easily find the number of unique differences possible.

**Claim:** There can exist at most 2 pairs where an element A\_i acts as a second maximum element. Those possible pairs are (A\_L, A\_i) and (A\_R, A\_i) where A\_L is the first greater (or equal) element on the left side of A\_i, whereas A\_R is the first greater (or equal) element on the right side of A\_i in the array.

> **Proof**
>
> Consider an array A of N numbers such that:
> 
> A\_1,....A\_L,A\_{L+1},....,A\_i,...,A\_{R-1},A\_R,....A\_N
> 
> Now, Suppose for A\_i, the next greater (or equal) element on the left side is A\_L, and the next greater (or equal) element on the right side is A\_R.
> 
> Initially, we have a subarray [A\_i, A\_{i+1}.., A\_R] such that the maximum element is A\_R and the second maximum element is A\_i since max(A\_i, A\_{i+1}.., A\_R)=A\_R and max(A\_i, A\_{i+1}.., A\_{R-1})=A\_i.
> 
> Now let us try adding elements on this subarray as we were doing in subtask 1.
> 
> **Case 1:** When A\_{R+1}\>A\_R
> 
> - In this case, A\_i will no longer remain the second maximum element as the A\_{R+1} will be the maximum element of the new subarray and A\_R will be the second maximum element.
> 
> **Case 1:** When A\_{R+1}\<A\_R and A\_{R+1}\>A\_i
> 
> - In this case, A\_i will no longer remain the second maximum element as the A\_{R+1} will be the second maximum element of this new subarray since A\_{R+1}\>A\_i.
> 
> **Case 3:** When A\_{R+1}\<A\_R and A\_{R+1}\<A\_i
> 
> - In this case, there will be no changes i.e A\_i will be the second maximum element and A\_R will be the maximum element.
> 
> We can clearly see for all the cases when A\_i is the second maximum element then only and only A\_R is the maximum element and that happens in **Case 3**. For other cases, A\_i no longer remains the second maximum element.
> 
> - Similarly, we can prove for the left side i.e when we have a subarray [A\_L, A\_{L+1}.., A\_i] such that the maximum element is A\_L and the second maximum element is A\_i. Now when we keep adding elements on the left side of this subarray similar cases appear.
> 
> - For all the subarray that has staring index greater than L and ending index less than R, and containing A\_i as the element of the subarray. In those cases, A\_i will be the maximum element as max(A\_{L+1},..., A\_i.., A\_{R-1})=A\_i
> 
> - For such subarray that contains both A\_L and A\_R, then as A\_i is smaller than both A\_L and A\_R. Hence A\_i won’t be acting as the second maximum element.
> 
> Hence there can exist at most 2 pairs where an element A\_i acts as a second maximum element. Those possible pairs are (A\_L, A\_i) and (A\_R, A\_i) where A\_L is the first greater (or equal) element on the left side of A\_i, whereas A\_R is the first greater (or equal) element on the right side of A\_i in the array.

So, We are left with finding A\_L and A\_R for every element of an array, which can be done in a single traversal of an array using a stack as explained [here](https://www.geeksforgeeks.org/next-greater-element/)

Finally, find out the difference for every pair of the maximum and second maximum elements and output the number of unique differences possible.

> **Time Complexity**
>
> O(N) per test case

# TIME COMPLEXITY:

O(N) per test case.

# SOLUTIONS:

> **Setter**
>
> ```auto
> #include <bits/stdc++.h>
> using namespace std;
> #define int long long
> #define pb push_back
> #define sz(x) ((int)x.size())
> #define endl "\n"
> #define inf (1LL<<62)
> #define ninf (-inf)
> 
> template<typename Tleaf>
> void print(Tleaf &&leaf, int n)
> {
> for(int i = 1; i <= n; i++)
> cout << leaf[i] << " \n"[i==n];
> }
> 
> template<typename Tleaf>
> void print(Tleaf &&leaf, int n, int m)
> {
> for(int i = 1; i <= n; i++)
> print(leaf[i], m);
> }
> 
> const int nax = 100005;
> int a[nax];
> 
> int32_t main()
> {
> ios::sync_with_stdio(false);
> cin.tie(0);
> int t;
> cin >> t;
> while(t--)
> {
> int n;
> cin >> n;
> for(int i = 1; i <= n; i++)
> cin >> a[i];
> set<int> s;
> stack<int> p;
> for(int i = 1; i <= n; i++)
> {
> while(sz(p) && p.top() <= a[i])
> {
> s.insert(a[i]-p.top());
> p.pop();
> }
> p.push(a[i]);
> }
> while(!p.empty())
> p.pop();
> reverse(a+1, a+n+1);
> for(int i = 1; i <= n; i++)
> {
> while(sz(p) && p.top() <= a[i])
> {
> s.insert(a[i]-p.top());
> p.pop();
> }
> p.push(a[i]);
> }
> cout << sz(s) << "\n";
> }
> }
> 
> ```

> **Tester**
>
> ```auto
> #include <bits/stdc++.h>
> using namespace std;
> #include <ext/pb_ds/assoc_container.hpp>
> #include <ext/pb_ds/tree_policy.hpp>
> #include <ext/rope>
> using namespace __gnu_pbds;
> using namespace __gnu_cxx;
> #ifndef rd
> #define trace(...)
> #define endl '\n'
> #endif
> #define pb push_back
> #define fi first
> #define se second
> #define int long long
> typedef long long ll;
> typedef long double f80;
> #define double long double
> #define pii pair<int,int>
> #define pll pair<ll,ll>
> #define sz(x) ((long long)x.size())
> #define fr(a,b,c) for(int a=b; a<=c; a++)
> #define rep(a,b,c) for(int a=b; a<c; a++)
> #define trav(a,x) for(auto &a:x)
> #define all(con) con.begin(),con.end()
> const ll infl=0x3f3f3f3f3f3f3f3fLL;
> const int infi=0x3f3f3f3f;
> //const int mod=998244353;
> const int mod=1000000007;
> typedef vector<int> vi;
> typedef vector<ll> vl;
>  
> typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
> auto clk=clock();
> mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
> int rng(int lim) {
> uniform_int_distribution<int> uid(0,lim-1);
> return uid(rang);
> }
> int powm(int a, int b) {
> int res=1;
> while(b) {
> if(b&1)
> res=(res*a)%mod;
> a=(a*a)%mod;
> b>>=1;
> }
> return res;
> }
>  
> long long readInt(long long l, long long r, char endd) {
> long long x=0;
> int cnt=0;
> int fi=-1;
> bool is_neg=false;
> while(true) {
> char g=getchar();
> if(g=='-') {
> assert(fi==-1);
> is_neg=true;
> continue;
> }
> if('0'<=g&&g<='9') {
> x*=10;
> x+=g-'0';
> if(cnt==0) {
> fi=g-'0';
> }
> cnt++;
> assert(fi!=0 || cnt==1);
> assert(fi!=0 || is_neg==false);
>  
> assert(!(cnt>19 || ( cnt==19 && fi>1) ));
> } else if(g==endd) {
> if(is_neg) {
> x=-x;
> }
> assert(l<=x&&x<=r);
> return x;
> } else {
> assert(false);
> }
> }
> }
> string readString(int l, int r, char endd) {
> string ret="";
> int cnt=0;
> while(true) {
> char g=getchar();
> assert(g!=-1);
> if(g==endd) {
> break;
> }
> cnt++;
> ret+=g;
> }
> assert(l<=cnt&&cnt<=r);
> return ret;
> }
> long long readIntSp(long long l, long long r) {
> return readInt(l,r,' ');
> }
> long long readIntLn(long long l, long long r) {
> return readInt(l,r,'\n');
> }
> string readStringLn(int l, int r) {
> return readString(l,r,'\n');
> }
> string readStringSp(int l, int r) {
> return readString(l,r,' ');
> }
>  
> int sum_n=0;
> pii a[100005];
> int le[100005],ri[100005];
> int leg[100005],rig[100005];
> void solve() {
> int n=readIntLn(2,100000);
> sum_n+=n;
> assert(sum_n<=1000'000);
> fr(i,1,n) {
> if(i!=n)
> a[i].fi=readIntSp(1,1000'000'000);
> else
> a[i].fi=readIntLn(1,1000'000'000);
> a[i].se=i;
> }
> set<pii> qu,qu1;
> fr(i,1,n) {
> while(qu1.size()&&(*qu1.begin())<a[i]) {
> rig[(*qu1.begin()).se]=i;
> qu1.erase(qu1.begin());
> }
> while(qu.size()&&(*qu.begin())<a[i]) {
> ri[(*qu.begin()).se]=i;
> qu1.insert(*qu.begin());
> qu.erase(qu.begin());
> }
> qu.insert(a[i]);
> }
> while(qu.size()) {
> ri[(*qu.begin()).se]=n+1;
> qu1.insert(*qu.begin());
> qu.erase(qu.begin());
> }
> while(qu1.size()) {
> rig[(*qu1.begin()).se]=n+1;
> qu1.erase(qu1.begin());
> }
> for(int i=n; i>0; i--) {
> while(qu1.size()&&(*qu1.begin())<a[i]) {
> leg[(*qu1.begin()).se]=i;
> qu1.erase(qu1.begin());
> }
> while(qu.size()&&(*qu.begin())<a[i]) {
> le[(*qu.begin()).se]=i;
> qu1.insert(*qu.begin());
> qu.erase(qu.begin());
> }
> qu.insert(a[i]);
> }
> while(qu.size()) {
> le[(*qu.begin()).se]=0;
> qu1.insert(*qu.begin());
> qu.erase(qu.begin());
> }
> while(qu1.size()) {
> leg[(*qu1.begin()).se]=0;
> qu1.erase(qu1.begin());
> }
> int ans=0;
> set<int> anser;
> fr(i,1,n) {
> if(le[i]!=0)
> anser.insert(a[le[i]].fi-a[i].fi);
> if(ri[i]!=n+1)
> anser.insert(a[ri[i]].fi-a[i].fi);
> // trace(le[i],leg[i],ri[i],rig[i]);
> // ans+=(ri[i]-le[i]-1)*a[i].fi;
> // trace(ans);
> // ans-=((rig[i]-ri[i])*(i-le[i])*a[i].fi);
> // ans-=((le[i]-leg[i])*(ri[i]-i)*a[i].fi);
> // ans-=a[i].fi;
> // trace(ans);
> }
> cout<<sz(anser)<<endl;
> //	cout<<ans<<endl;
> }
>  
> signed main() {
> ios_base::sync_with_stdio(0),cin.tie(0);
> srand(chrono::high_resolution_clock::now().time_since_epoch().count());
> cout<<fixed<<setprecision(10);
> int t=readIntLn(1,100000);
> //	int t;
> //	cin>>t;
> fr(i,1,t)
> solve();
> #ifdef rd
> cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
> #endif
> }
>  
> 
> ```

> **Editorialist**
>
> ```auto
> #include<bits/stdc++.h>
> using namespace std;
>  
> #define int long long
>  
> const int mxN=1e5+5;
> int a[mxN];
> int n;
> int lft[mxN];
> int rght[mxN];
>  
> int32_t main()
> {
> ios_base::sync_with_stdio(0);
> cin.tie(0);
>  
> int t;
> cin>>t;
>  
> while(t--)
> {
> cin>>n;
>  
> for(int i=1;i<=n;i++)
> {
> cin>>a[i];
> }
>  
> set <int> ans;
>  
> stack <int> s;
>  
> for(int i=1;i<=n;i++)
> {
> while(s.size()>0 && s.top()<a[i])
> s.pop();
>  
> if(s.size()>0)
> lft[i]=s.top();
> else
> lft[i]=-1;
>  
> s.push(a[i]);
> }
>  
> while(s.size()>0)
> s.pop();
>  
> for(int i=n;i>=1;i--)
> {
> while(s.size()>0 && s.top()<a[i])
> s.pop();
>  
> if(s.size()>0)
> rght[i]=s.top();
> else
> rght[i]=-1;
>  
> s.push(a[i]);
> }
>  
> for(int i=1;i<=n;i++)
> {
> if(lft[i]!=-1)
> ans.insert(lft[i]-a[i]);
> if(rght[i]!=-1)
> ans.insert(rght[i]-a[i]);
> }
>  
> cout<<ans.size()<<"\n";
> }
>  
> return 0;
> }
> 
> ```

# VIDEO EDITORIAL:
https://www.youtube.com/embed/t9JbrjKXKks

---

<div class="post-metadata">

**Author:** ![kid\_delta0001](https://discuss.codechef.com/user_avatar/discuss.codechef.com/kid_delta0001/32/152330_2.png) [@kid\_delta0001](https://discuss.codechef.com/u/kid_delta0001)\
**Post date:** [February 27, 2021, 5:30pm UTC](https://discuss.codechef.com/t/sedmax-editorial/86099/2 "2021-02-27T17:30:21Z")

</div>

Great solution by setter in O(N), an O(N log N) solution to the (almost) exact problem is unfortunately also available on GFG [https://www.geeksforgeeks.org/find-all-unique-pairs-of-maximum-and-second-maximum-elements-over-all-sub-arrays-in-onlogn/](https://www.geeksforgeeks.org/find-all-unique-pairs-of-maximum-and-second-maximum-elements-over-all-sub-arrays-in-onlogn/)

---

<div class="post-metadata">

**Author:** ![aloo08051999](https://discuss.codechef.com/user_avatar/discuss.codechef.com/aloo08051999/32/111310_2.png) [@aloo08051999](https://discuss.codechef.com/u/aloo08051999)\
**Post date:** [February 27, 2021, 5:37pm UTC](https://discuss.codechef.com/t/sedmax-editorial/86099/3 "2021-02-27T17:37:22Z")

</div>

Now I understand how these many AC solutions for the problem in Div2.

---

<div class="post-metadata">

**Author:** ![ramandeep8421](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ramandeep8421/32/237365_2.png) [@ramandeep8421](https://discuss.codechef.com/u/ramandeep8421)\
**Post date:** [February 27, 2021, 5:43pm UTC](https://discuss.codechef.com/t/sedmax-editorial/86099/4 "2021-02-27T17:43:18Z")

</div>

ohhh this was the solution , i was thinking it seems a little bit standard ☹

---

<div class="post-metadata">

**Author:** ![manoj\_269](https://discuss.codechef.com/user_avatar/discuss.codechef.com/manoj_269/32/281401_2.png) [@manoj\_269](https://discuss.codechef.com/u/manoj_269)\
**Post date:** [February 27, 2021, 5:44pm UTC](https://discuss.codechef.com/t/sedmax-editorial/86099/5 "2021-02-27T17:44:33Z")

</div>

lol ☹

---

<div class="post-metadata">

**Author:** ![dhrub\_kumar](https://discuss.codechef.com/user_avatar/discuss.codechef.com/dhrub_kumar/32/24644_2.png) [@dhrub\_kumar](https://discuss.codechef.com/u/dhrub_kumar)\
**Post date:** [February 27, 2021, 5:54pm UTC](https://discuss.codechef.com/t/sedmax-editorial/86099/6 "2021-02-27T17:54:52Z")

</div>

Well if you look closely both the solution are almost same , the authors one and the GFG one , there also the Complexity is O(NlogN) only because of using set , using unordered set can get it down to O(N)

---

<div class="post-metadata">

**Author:** ![akash333](https://discuss.codechef.com/user_avatar/discuss.codechef.com/akash333/32/29304_2.png) [@akash333](https://discuss.codechef.com/u/akash333)\
**Post date:** [February 27, 2021, 6:38pm UTC](https://discuss.codechef.com/t/sedmax-editorial/86099/7 "2021-02-27T18:38:24Z")

</div>

I solved it using a constructive algo in O(NLOGN). Sort in descending the values along with their indexes and iterate this array to find the left and right greater elements incrementally. Here is my solution - [CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/43170109)  
I was astonished to see everyone using stack all other solutions!

---

<div class="post-metadata">

**Author:** ![smit](https://discuss.codechef.com/user_avatar/discuss.codechef.com/smit/32/24644_2.png) [@smit](https://discuss.codechef.com/u/smit)\
**Post date:** [February 27, 2021, 8:21pm UTC](https://discuss.codechef.com/t/sedmax-editorial/86099/8 "2021-02-27T20:21:57Z")

</div>

```
#include <iostream>
#include <vector>
#include<stack>
#include<set>
#include<cmath>
using namespace std;
int main()
{int t;
    cin>>t;
    while(t--){
      int n;
      cin>>n;
      int a[n];
      for(int i=0;i<n;i++)
        {cin>>a[i];}
        stack<int>s;set<int>u;
        for(int i=0;i<n;i++){
            if(s.size()==0){
                s.push(a[i]);
            }
            else if(s.size()==1){
                u.insert(abs(s.top()-a[i]));
                s.push(a[i]);
            }
            else if(s.top()>=a[i])
            {
                u.insert(abs(s.top()-a[i]));
                s.push(a[i]);
            }
            else{
                while( s.size()>0 && s.top()<a[i]){
                        u.insert(abs(s.top()-a[i]));
                        s.pop();
                }
                if(s.size()>0)
                u.insert(abs(s.top()-a[i]));
                s.push(a[i]);
            }}
        cout<<(int)u.size()<<endl;}}

```

Can someone please help me figure out the flaw in this implementation? If possible, please provide a test case that would fail on this.

---

<div class="post-metadata">

**Author:** ![aniket\_0206](https://discuss.codechef.com/user_avatar/discuss.codechef.com/aniket_0206/32/259059_2.png) [@aniket\_0206](https://discuss.codechef.com/u/aniket_0206)\
**Post date:** [February 28, 2021, 3:25am UTC](https://discuss.codechef.com/t/sedmax-editorial/86099/9 "2021-02-28T03:25:54Z")

</div>

Will you please explain how you reached upto this conclusion …  
Thanks in advance

---

<div class="post-metadata">

**Author:** ![girishgarg](https://discuss.codechef.com/user_avatar/discuss.codechef.com/girishgarg/32/28183_2.png) [@girishgarg](https://discuss.codechef.com/u/girishgarg)\
**Post date:** [February 28, 2021, 5:03am UTC](https://discuss.codechef.com/t/sedmax-editorial/86099/10 "2021-02-28T05:03:31Z")

</div>

next level

---

<div class="post-metadata">

**Author:** ![akshitm16](https://discuss.codechef.com/user_avatar/discuss.codechef.com/akshitm16/32/239171_2.png) [@akshitm16](https://discuss.codechef.com/u/akshitm16)\
**Post date:** [February 28, 2021, 5:09am UTC](https://discuss.codechef.com/t/sedmax-editorial/86099/11 "2021-02-28T05:09:07Z")

</div>

I did exactly same.

---

<div class="post-metadata">

**Author:** ![akash333](https://discuss.codechef.com/user_avatar/discuss.codechef.com/akash333/32/29304_2.png) [@akash333](https://discuss.codechef.com/u/akash333)\
**Post date:** [February 28, 2021, 5:38am UTC](https://discuss.codechef.com/t/sedmax-editorial/86099/12 "2021-02-28T05:38:14Z")

</div>

@aniket_0206 The concept is basically the same (fixing the second max). You can sort descending order the values and iteratively fix the second max element. Meanwhile, you have an indices array of elements greater than the current element (because you are iterating descending thats possible, initially that array is empty). You can do a binary search and find the indices greater and smaller than the element in iteration and that would produce new diffs needed. Update the current element’s index in the indices array (in sorted order) and proceed for the next iteration.

---

<div class="post-metadata">

**Author:** ![girishgarg](https://discuss.codechef.com/user_avatar/discuss.codechef.com/girishgarg/32/28183_2.png) [@girishgarg](https://discuss.codechef.com/u/girishgarg)\
**Post date:** [February 28, 2021, 6:45am UTC](https://discuss.codechef.com/t/sedmax-editorial/86099/13 "2021-02-28T06:45:01Z")

</div>

explain with eg?

---

<div class="post-metadata">

**Author:** ![dheeraj\_jha](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@dheeraj\_jha](https://discuss.codechef.com/u/dheeraj_jha)\
**Post date:** [February 28, 2021, 9:25am UTC](https://discuss.codechef.com/t/sedmax-editorial/86099/14 "2021-02-28T09:25:07Z")

</div>

Tester is writing the shittiest code possible.

---

<div class="post-metadata">

**Author:** ![azhar316](https://discuss.codechef.com/user_avatar/discuss.codechef.com/azhar316/32/24644_2.png) [@azhar316](https://discuss.codechef.com/u/azhar316)\
**Post date:** [February 28, 2021, 10:37am UTC](https://discuss.codechef.com/t/sedmax-editorial/86099/15 "2021-02-28T10:37:46Z")

</div>

This is not a **easy-medium** level problem. It is at least **medium** level problem as we first have to observe that every element can be second maximum at most 2 times and then know the trick to find the two maximum elements of each element in O(N) time.

---

<div class="post-metadata">

**Author:** ![phantom\_07](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@phantom\_07](https://discuss.codechef.com/u/phantom_07)\
**Post date:** [February 28, 2021, 10:38am UTC](https://discuss.codechef.com/t/sedmax-editorial/86099/16 "2021-02-28T10:38:54Z")

</div>

```auto
#include<bits/stdc++.h>
#define line cout<<endl;
#define space cout<<" ";
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PI 3.141592653589793238
typedef long long int ll;

using namespace std;

const ll N = 1e9+7;

ll nextgreater[100000+5]; 
ll previousgreater[100000+5]; 

void solve()
{
  memset(nextgreater,-1,sizeof(nextgreater)); 
  memset(previousgreater,-1,sizeof(previousgreater)); 
  ll n; 
  cin>>n; 

  vector<ll> v(n); 
  for(int i=0;i<n;i++){
    cin>>v[i]; 
  }

  stack<ll> selement;
  stack<ll> sindex;  
  for(int i=0;i<n;i++){
    if(selement.empty()){
      selement.push(v[i]); 
      sindex.push(i); 
    }
    else{
      if(v[i] > selement.top()){
        while(!selement.empty() && v[i] >= selement.top()){
          ll index = sindex.top(); 
          nextgreater[index] = v[i]; 
          selement.pop(); 
          sindex.pop(); 
        }
        selement.push(v[i]); 
        sindex.push(i); 
      }
      else{
        selement.push(v[i]); 
        sindex.push(i); 
      }
      
      
    }
  }
  while(!selement.empty()){
    selement.pop(); 
  }
  while(!sindex.empty()){
    sindex.pop(); 
  }

  for(int i=n-1;i>=0;i--){
    if(selement.empty()){
      selement.push(v[i]); 
      sindex.push(i); 
    }
    else{
      if(v[i] > selement.top()){
        while(!selement.empty() && v[i] >= selement.top()){
          ll index = sindex.top(); 
          previousgreater[index] = v[i]; 
          selement.pop(); 
          sindex.pop(); 
        }
        selement.push(v[i]); 
        sindex.push(i); 
      }
      else{
        selement.push(v[i]); 
        sindex.push(i); 
      }
      
      
    }
  }

  set<ll> ansset; 
  for(int i=0;i<n;i++){
    if(nextgreater[i] != -1){
      ansset.insert(nextgreater[i] - v[i]); 
    }
    if(previousgreater[i] != -1){
      ansset.insert(previousgreater[i] - v[i]); 
    }
  }

  cout<<ansset.size(); 
}

int main()
{
   fast;
   ll t;
   // t = 1;
   cin>>t;

   while(t--)
   {
       solve();
       cout<<endl;
   }

}

```

Can someone tell what is wrong in my solution plz

---

<div class="post-metadata">

**Author:** ![akshitm16](https://discuss.codechef.com/user_avatar/discuss.codechef.com/akshitm16/32/239171_2.png) [@akshitm16](https://discuss.codechef.com/u/akshitm16)\
**Post date:** [February 28, 2021, 10:57am UTC](https://discuss.codechef.com/t/sedmax-editorial/86099/17 "2021-02-28T10:57:53Z")

</div>

Consider

> **tc**
>
> 2  
> 1 1

---

<div class="post-metadata">

**Author:** ![phantom\_07](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@phantom\_07](https://discuss.codechef.com/u/phantom_07)\
**Post date:** [February 28, 2021, 11:02am UTC](https://discuss.codechef.com/t/sedmax-editorial/86099/18 "2021-02-28T11:02:34Z")

</div>

```auto
#include<bits/stdc++.h>
#define line cout<<endl;
#define space cout<<" ";
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PI 3.141592653589793238
typedef long long int ll;

using namespace std;

const ll N = 1e9+7;

ll nextgreater[100000+5]; 
ll previousgreater[100000+5]; 

void solve()
{
  memset(nextgreater,-1,sizeof(nextgreater)); 
  memset(previousgreater,-1,sizeof(previousgreater)); 
  ll n; 
  cin>>n; 

  vector<ll> v(n); 
  for(int i=0;i<n;i++){
    cin>>v[i]; 
  }

  // cout<<"hello world"; line; 

  stack<ll> selement;
  stack<ll> sindex;  

  for(int i=0;i<n;i++){
    if((int)selement.size() == 0){
      selement.push(v[i]); 
      sindex.push(i); 
    }
    else{
      if(v[i] >= selement.top()){
        while((int)selement.size() > 0 && v[i] >= selement.top()){
          nextgreater[sindex.top()] = v[i]; 
          selement.pop(); 
          sindex.pop(); 
        }
     }

     selement.push(v[i]); 
     sindex.push(i); 
   }
  }

  // cout<<"next greater is done: "; line; 

  while((int)selement.size() > 0){
    selement.pop(); 
  }
  while((int)selement.size() > 0){
    sindex.pop(); 
  }

  // cout<<"made empty: "; line; 

  for(int i=n-1;i>=0;i--){
    if((int)selement.size() == 0){
      selement.push(v[i]); 
      sindex.push(i); 
    }
    else{
      if(v[i] >= selement.top()){
        while((int)selement.size() > 0 && v[i] >= selement.top()){
          previousgreater[sindex.top()] = v[i]; 
          selement.pop(); 
          sindex.pop(); 
        }
      }

      selement.push(v[i]); 
      sindex.push(i); 
      
    }
  }
  // cout<<"previous greater id one: ";line; 

  unordered_set<ll> ansset; 
  for(int i=0;i<n;i++){
    if(nextgreater[i] != -1){
      ansset.insert(nextgreater[i] - v[i]); 
    }
    if(previousgreater[i] != -1){
      ansset.insert(previousgreater[i] - v[i]); 
    }
  }

  cout<<ansset.size(); 
}

int main()
{
   fast;
   ll t;
   // t = 1;
   cin>>t;

   while(t--)
   {
       solve();
       cout<<endl;
   }

}

```

I have modified the soluntion just a bit  
2  
1 1  
this test I’m getting ans 1

this is also getting TLE on some case in subtask 2, but the solution is almost identical to author’s solution

---

<div class="post-metadata">

**Author:** ![akshitm16](https://discuss.codechef.com/user_avatar/discuss.codechef.com/akshitm16/32/239171_2.png) [@akshitm16](https://discuss.codechef.com/u/akshitm16)\
**Post date:** [February 28, 2021, 11:03am UTC](https://discuss.codechef.com/t/sedmax-editorial/86099/19 "2021-02-28T11:03:43Z")

</div>

That’s what the correct solution supposed to get.

---

<div class="post-metadata">

**Author:** ![phantom\_07](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@phantom\_07](https://discuss.codechef.com/u/phantom_07)\
**Post date:** [February 28, 2021, 11:08am UTC](https://discuss.codechef.com/t/sedmax-editorial/86099/20 "2021-02-28T11:08:19Z")

</div>

Yes for the test case you suggested I’m getting correct ans for above solution , but after submitting it m getting TLE on 1 testcase of subtask 2

 ![Screenshot (920)](https://s3.amazonaws.com/discourseproduction/original/3X/0/f/0f161188e3907f1ee5620876c858687dc328215f.png)

[Next page](https://discuss.codechef.com/t/sedmax-editorial/86099.md?page=2)