Manhattan Subarrays Codeforces Solution

Manhattan Subarrays Codeforces Solution

Suppose you have two points p=(xp,yp)p=(xp,yp) and q=(xq,yq)q=(xq,yq). Let’s denote the Manhattan distance between them as d(p,q)=|xp−xq|+|yp−yq|d(p,q)=|xp−xq|+|yp−yq|.

Let’s say that three points pp, qq, rr form a bad triple if d(p,r)=d(p,q)+d(q,r)d(p,r)=d(p,q)+d(q,r).

Let’s say that an array b1,b2,…,bmb1,b2,…,bm is good if it is impossible to choose three distinct indices ii, jj, kk such that the points (bi,i)(bi,i), (bj,j)(bj,j) and (bk,k)(bk,k) form a bad triple.

You are given an array a1,a2,…,ana1,a2,…,an. Calculate the number of good subarrays of aa. A subarray of the array aa is the array al,al+1,…,aral,al+1,…,ar for some 1≤l≤r≤n1≤l≤r≤n.

Note that, according to the definition, subarrays of length 11 and 22 are good.Input

The first line contains one integer tt (1≤t≤50001≤t≤5000) — the number of test cases.

The first line of each test case contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the length of array aa.

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109).

It’s guaranteed that the sum of nn doesn’t exceed 2⋅1052⋅105.Output

For each test case, print the number of good subarrays of array aa.

Example

input

3
4
2 4 1 3
5
6 9 1 9 6
2
13 37

output

10
12
3

Note

In the first test case, it can be proven that any subarray of aa is good. For example, subarray [a2,a3,a4][a2,a3,a4] is good since it contains only three elements and:

• d((a2,2),(a4,4))=|4−3|+|2−4|=3d((a2,2),(a4,4))=|4−3|+|2−4|=3 << d((a2,2),(a3,3))+d((a3,3),(a4,4))=3+1+2+1=7d((a2,2),(a3,3))+d((a3,3),(a4,4))=3+1+2+1=7;
• d((a2,2),(a3,3))d((a2,2),(a3,3)) << d((a2,2),(a4,4))+d((a4,4),(a3,3))d((a2,2),(a4,4))+d((a4,4),(a3,3));
• d((a3,3),(a4,4))d((a3,3),(a4,4)) << d((a3,3),(a2,2))+d((a2,2),(a4,4))d((a3,3),(a2,2))+d((a2,2),(a4,4));

In the second test case, for example, subarray [a1,a2,a3,a4][a1,a2,a3,a4] is not good, since it contains a bad triple (a1,1)(a1,1), (a2,2)(a2,2), (a4,4)(a4,4):

• d((a1,1),(a4,4))=|6−9|+|1−4|=6d((a1,1),(a4,4))=|6−9|+|1−4|=6;
• d((a1,1),(a2,2))=|6−9|+|1−2|=4d((a1,1),(a2,2))=|6−9|+|1−2|=4;
• d((a2,2),(a4,4))=|9−9|+|2−4|=2d((a2,2),(a4,4))=|9−9|+|2−4|=2;

So, d((a1,1),(a4,4))=d((a1,1),(a2,2))+d((a2,2),(a4,4))d((a1,1),(a4,4))=d((a1,1),(a2,2))+d((a2,2),(a4,4)).

Solution

#include <bits/stdc++.h>
using namespace std;

int a[200007];

int main() {
    // freopen("in.txt","r",stdin); 
    // freopen("out.txt","w",stdout);
    ios::sync_with_stdio(false);
    int t;
    cin>>t;

    while(t--){
        int n;
        cin>>n;
        memset(a,0,sizeof(a));
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        long long ans=0;
        ans+=n;
        if(n>=2){
            ans+=n-1;
            if(n>=3){
                for(int i=0;i<n-2;i++){
                    if(a[i+1]>max(a[i],a[i+2])||a[i+1]<min(a[i],a[i+2])){
                        ans++;
                    }
                }
                if(n>=4){
                    for(int i=0;i<n-3;i++){
                        if(a[i+1]>max(a[i],max(a[i+2],a[i+3]))&&a[i+2]<min(a[i],min(a[i+1],a[i+3]))||a[i+1]<min(a[i],min(a[i+2],a[i+3]))&&a[i+2]>max(a[i],max(a[i+1],a[i+3]))){
                            ans++;
                        }
                    }
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

Educational Codeforces Round 111 (Rated for Div. 2)

• Excellent Arrays Codeforces Solution
• Stringforces Codeforces Solution
• Jumping Around Codeforces Solution
• Manhattan Subarrays Codeforces Solution
• Maximum Cost Deletion Codeforces Solution
• Find The Array Codeforces Solution