Page Contents

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

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

Manhattan Subarrays Codeforces Solution

Solution

Educational Codeforces Round 111 (Rated for Div. 2)

Leave a Comment Cancel reply