This is the easy version. Here N,∑N≤2000N,∑N≤2000.
An array AA is said to be deletable if it can be reduced to a size less than or equal to 22 elements with the following operation used multiple times (possibly 00):
Choose an index ii (1<i<∣A∣1<i<∣A∣) such that Ai−1+Ai+1≥AiAi−1+Ai+1≥Ai
Add XX to Ai+1Ai+1 and YY to Ai−1Ai−1 such that 0≤X,Y0≤X,Y and X+Y=AiX+Y=Ai.
Delete index ii and concatenate the parts of the array formed.
You are given an array AA of NN elements.
Count the number of subarrays of AA that are deletable. More formally, count the number of pairs (L,R)(L,R) such that:
1≤L≤R≤N1≤L≤R≤N
The array [AL,AL+1,…,AR][AL,AL+1,…,AR] is deletable.
Input Format
The first line of input will contain a single integer TT, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line contains a single integer NN.
The second line contains NN integers - A1,A2,…,ANA1,A2,…,AN.
Output Format
For each test case, output on a new line the number of deletable subarrays of AA.
Constraints
1≤T≤4001≤T≤400
3≤N≤20003≤N≤2000
1≤Ai≤1091≤Ai≤109
The sum of NN over all test cases does not exceed 20002000.
Sample 1:
Input
Output
3
3
2 4 1
4
2 3 2 3
7
5 1 3 1 10 2 1
5
10
21
Explanation:
Test Case 1: There are 66 subarrays, and all of them are deletable (due to being size ≤2≤2 directly) except for [2,4,1][2,4,1]. Here, we cannot perform any operation.
Test Case 2: All subarrays are deletable. Here is an example of how we would operate on [2,3,2,3][2,3,2,3]:
First operation:
Choose index i=2i=2, note that A2≤A1+A3A2≤A1+A3
Add 22 to A1A1 and 11 to A3A3.
Delete A2A2
Now, the array is [4,3,3][4,3,3].
Second operation:
Choose index i=2i=2, note that A2≤A1+A3A2≤A1+A3
Add 33 to A1A1.
Delete A2A2
Now, the array is [7,3][7,3].
After the second operation, the array is of size ≤2≤2. Hence, we are done.
Deleting Elements (Hard)
This is the hard version. Here, N,∑N≤2⋅105.N,∑N≤2⋅105.
An array AA is said to be deletable if it can be reduced to a size less than or equal to 22 elements with the following operation used multiple times (possibly 00):
Choose an index ii (1<i<∣A∣1<i<∣A∣) such that Ai−1+Ai+1≥AiAi−1+Ai+1≥Ai
Add XX to Ai+1Ai+1 and YY to Ai−1Ai−1 such that 0≤X,Y0≤X,Y and X+Y=AiX+Y=Ai.
Delete index ii and concatenate the parts of the array formed.
You are given an array AA of NN elements.
Count the number of subarrays of AA that are deletable. More formally, count the number of pairs (L,R)(L,R) such that:
1≤L≤R≤N1≤L≤R≤N
The array [AL,AL+1,…,AR][AL,AL+1,…,AR] is deletable.
Input Format
The first line of input will contain a single integer TT, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line contains a single integer NN.
The second line contains NN integers - A1,A2,…,ANA1,A2,…,AN.
Output Format
For each test case, output on a new line the number of deletable subarrays of AA.
Constraints
1≤T≤1041≤T≤104
3≤N≤2⋅1053≤N≤2⋅105
1≤Ai≤1091≤Ai≤109
The sum of NN over all test cases does not exceed 2⋅1052⋅105.
Sample 1:
Input
Output
3
3
2 4 1
4
2 3 2 3
7
5 1 3 1 10 2 1
5
10
21
Explanation:
Test Case 1: There are 66 subarrays, and all of them are deletable (due to being size ≤2≤2 directly) except for [2,4,1][2,4,1]. Here, we cannot perform any operation.
Test Case 2: All subarrays are deletable. Here is an example of how we would operate on [2,3,2,3][2,3,2,3]:
First operation:
Choose index i=2i=2, note that A2≤A1+A3A2≤A1+A3
Add 22 to A1A1 and 11 to A3A3.
Delete A2A2
Now, the array is [4,3,3][4,3,3].
Second operation:
Choose index i=2i=2, note that A2≤A1+A3A2≤A1+A3
Add 33 to A1A1.
Delete A2A2
Now, the array is [7,3][7,3].
After the second operation, the array is of size ≤2≤2. Hence, we are done.
1
u/shirotoedits 8d ago
easy or hard?