# Manhattan Subarrays Codeforces Solution

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

```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;

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)

### 1 thought on “Manhattan Subarrays Codeforces Solution”

1. If some one needs expert view regarding blogging
then i suggest him/her to pay a quick visit this web site, Keep up
the good work.