PROBLEM LINK:
Setter- Erfan Alimohammadi
Tester- Roman Bilyi
Editorialist- Abhishek Pandey
DIFFICULTY:
EASY
PRE-REQUISITES:
PROBLEM:
Given an array A of size N, find number of ways to delete a non-empty subarray from it so that the remaining part of A is strictly increasing.
QUICK-EXPLANATION:
Key to AC- Don’t over-complicate the solution. Think in terms of, that, “If I start deleting from index i, then how many ways are possible?”
Maintain 2 arrays, Prefix[i] and Suffix[i] - where Prefix[i] will store true if subarray from [1,i] is strictly increasing, and similarly Suffix[i]=true if the subarray from [i,N] is strictly increasing. Note that, once Prefix[i]=false for any index i, it will remain false for every index after i as well. A vice-versa observation holds for Suffix[] array as well.
Notice that if Prefix[i]=false, then deleting a sub-array starting from index i will not yield a strictly increasing array (as its falsified before this index already). Hence, for every index starting from 1 (1-based indexing), as long as Prefix[i] is true, Binary search for the least index j such that A_j>A_i and array from index j onwards is strictly increasing. (This can be easily achieved by using our Suffix[j] array) . We can now delete N-j+1 subarrays from index (i+1) to index [j-1,N]. Note that, it is implicitly implied that j must be greater than (i+1).
Make sure to account for cases where you might delete an empty subarray (for some test cases) when i=0, or when you are deleting the first element of the array in operation as well.
(Note- I said the range [j-1,N] because you have the option to keep entire range [j,N] as well. In other words, starting from index i, you have to compulsorily delete upto index j-1. Thats the reason for +1 in the expression)
EXPLANATION:
We will first discuss the importance of Prefix[] and Suffix[] array. Once that is done, we will move on to the binary search part, touching upon little implementation details and summarize the editorial. The editorial uses 1-based \ indexing unless explicitly mentioned otherwise.
1. Maintaining the Prefix[] and Suffix[] array-
We define Prefix[i] to be true if the subarray from [1,i] is strictly increasing. Similarly, we maintain another array Suffix[], where Suffix[i] is true if the array from [i,N] is strictly increasing. The first step towards solution is to realize why they are needed in first place - hence give some time thinking of it. In case you are unable to grasp, the solution is below.
If you are still not clear about Role of Prefix & Suffix Arrays here
The rationale behind these two, is that, we only have those many starting positions to consider where Prefix[i]=true. Once Prefix[i] becomes false, it will never be true again because if subarray from [1,i] is not strictly increasing, then the subarray from [1,j] will never be strictly increasing either, for all j > i.
Hence, if we start from an index where Prefix[i]=false, then we cannot make the resulting array strictly increasing no matter what. Hence, starting from index 1, we can go upto only that index i till where Prefix[i] is true.
Similar reasoning holds for Suffix[] array as well. Try to think of it a little, in case you face any issue, the reasoning is there in bonus section. Look at it before proceeding to the next section if the purpose is not clear.
Once you are clear with the idea that what is the need of these arrays, or what do these arrays denote, proceed to the next section to see how they will be used.
2. Binary Searching-
Now, the things to note are that we can perform the operation only once, and the operation must remove a contiguous subarray. Starting from index 1, iterate along all indices i till which Prefix[i]=true. For all such indices, if we can find the index j, such that A_j>A_i and Suffix[j]=true (i.e. the subarray from index [j,N] is strictly increasing), then we are done! That is because, we can then claim that "We get (N-j+1) ways of removing sub-array from range [j-1,N]. Note that it is (j-1) here because A_j>A_i and Suffix[j]=true, which allow the final array formed by elements in range [1,i] \cup [j,N] to be strictly increasing as well! Iterating for all such valid i's will give us the final answer!
Now, the question reduces to, how will we find such a valid index j ? Easy, but perhaps unexpected for some newcomers - Binary Search!
Have a look at your Prefix[] and Suffix[] arrays. Prefix[] is initially true at i=1, and once it becomes false, it remains false till the end. Vice Versa holds for the Suffix[] array. Because of this, we can apply Binary Search on the array!
For Binary Search, we look for 2 things-
- Suffix[j] must be true.
- A_j must be strictly greater than A_i
The second part is very much valid even if original array A is unsorted (Why?). With this, all that is left is to code our binary search. Setter’s implementation is given below-
Setter's Binary Search
int lo = i + 1, hi = n + 1;
while (hi - lo > 1){
int mid = (lo + hi) >> 1;
if (pd[mid] == 1 and a[mid] > a[i]) //pd = Suffix Array
hi = mid;
else
lo = mid;
}
answer += n - lo + 1;
However, one thing is still left!!
Recall our interpretation! For every index i, we are fixing the starting point of the to-be-deleted subarray to (i+1). Got what I am trying to imply? Take it like this - For every index i, finding a j such that the array formed by [1,i] \cup [k,N], where j-1 \leq k \leq N. This means that the deleted sub-array is [i+1,k-1]. Can you think the corner case we are missing here? 
We are not deleting the first element here!! To account for this, just do another binary search without the A_{mid} > A_i condition, as all elements from index 1 upto index k will be deleted. (Alternate - What if we simply see for upto how many indices the Suffix[i] is 1 ?)
With this done, all that is left is to take care of implementation issues, for instance, if your implementation needs to handle the case of deleting an empty subarray, or getting an empty sub-array &etc.
SOLUTION
Setter
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
const int inf = 1e9 + 10;
bool dp[maxn], pd[maxn];
int a[maxn], t, n;
int main(){
ios_base::sync_with_stdio (false);
cin >> t;
while (t--) {
cin >> n;
dp[0] = 1;
a[0] = -inf;
for (int i = 1; i <= n; i++){
cin >> a[i];
dp[i] = (dp[i - 1] & (a[i] > a[i - 1]));
}
pd[n + 1] = 1;
a[n + 1] = inf;
for (int i = n; i >= 1; i--)
pd[i] = (pd[i + 1] & (a[i] < a[i + 1]));
ll answer = 0;
int lo = 0, hi = n + 1;
while (hi - lo > 1){
int mid = (lo + hi) >> 1;
if (pd[mid])
hi = mid;
else
lo = mid;
}
answer = (n - lo);
for (int i = 1; i <= n - 1; i++){
if (dp[i] == 0)
break;
int lo = i + 1, hi = n + 1;
while (hi - lo > 1){
int mid = (lo + hi) >> 1;
if (pd[mid] == 1 and a[mid] > a[i])
hi = mid;
else
lo = mid;
}
answer += n - lo + 1;
}
cout << answer - dp[n] << endl;
}
}
Tester
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
typedef long long Int;
typedef vector<int> VI;
typedef pair<int, int> PII;
const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000;
const Int LINF = INF * (Int) INF;
const int MAX = 100007;
const int MOD = 998244353;
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){
assert(cnt>0);
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,' ');
}
void assertEof(){
assert(getchar()==-1);
}
int main(int argc, char* argv[])
{
// freopen("in.txt", "r", stdin);
//ios::sync_with_stdio(false); cin.tie(0);
int t = readIntLn(1, 10);
FOR(tt,0,t)
{
int n = readIntLn(1, 100000);
VI A(n);
FOR(i,0,n)
{
if (i + 1 < n)
A[i] = readIntSp(-INF, INF);
else
A[i] = readIntLn(-INF, INF);
}
VI X;
int val = INF + 47;
X.push_back(val);
RFOR(i, n, 0)
{
if (A[i] >= val) break;
val = A[i];
X.push_back(val);
}
Int res = min(SZ(X) - 1, n - 1);
val = -INF - 47;
FOR(i,0,n)
{
if (A[i] <= val) break;
val = A[i];
while (SZ(X) && X.back() <= A[i]) X.pop_back();
res += min(SZ(X), n - 1 - i);
}
cout << res << endl;
}
assertEof();
cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
}
Time Complexity=O(NLogN) (Binary Search)
Space Complexity=O(N)
CHEF VIJJU’S CORNER 
Why we need the Suffix array
Similar to the Prefix[] array, the Suffix[] array highlights about number of suitable ending positions we have for sub-array to delete.
Exactly opposite to Prefix[] array, Suffix[] array is initially 0, and once it takes a value of 1, it will always be 1. This is because if the subarray in range [i,N] is strictly increasing, then so is the subarray in range [i+1,N]
If we put the ending point of the to-be-deleted subarray at some point where Suffix[i]=false AND Suffix[i+1] is NOT true, then the resulting subarray cannot be strictly increasing as the array in range [i+1,N] is not strictly increasing.
"Array A is not sorted, then how is Binary search Possible
Simple! Because this condition matters only if Suffix[i] is true! This means that the range the continuously increasing sub-array ending at index N. In other words the sub-array in which we are binary searching is strictly increasing, or sorted. Hence we are able to avoid wrong answer. Remember, we are not binary searching for some value in the entire array - we are binary searching in the sorted part of the array for some value greater than A[i]!
3.This Question is also solvable by using two-pointer technique! Give it a try and share your approach here 
4.What modifications can you think of, if I modify the problem as “the resulting sub-array must be strictly increasing, however, an error of 1 element is allowed”. Meaning, its ok if ignoring/deleting atmost 1 element, the resulting array after the operation becomes strictly increasing. How can we solve this problem?
Setter's Notes
We can solve the problem using Binary Search for appropriate index, or by two-pointers.
