题目链接：https://codeforces.com/contest/1550/problem/C
Suppose you have two points p=(xp,yp) and q=(xq,yq). Let’s denote the Manhattan distance between them as d(p,q)=|xp?xq|+|yp?yq|.
Let’s say that three points p, q, r form a bad triple if d(p,r)=d(p,q)+d(q,r).
Let’s say that an array b1,b2,…,bm is good if it is impossible to choose three distinct indices i, j, k such that the points (bi,i), (bj,j) and (bk,k) form a bad triple.
You are given an array a1,a2,…,an. Calculate the number of good subarrays of a. A subarray of the array a is the array al,al+1,…,ar for some 1≤l≤r≤n.
Note that, according to the definition, subarrays of length 1 and 2 are good.
Input
The first line contains one integer t (1≤t≤5000) — the number of test cases.
The first line of each test case contains one integer n (1≤n≤2?105) — the length of array a.
The second line of each test case contains n integers a1,a2,…,an (1≤ai≤109).
It’s guaranteed that the sum of n doesn’t exceed 2?105.
Output
For each test case, print the number of good subarrays of array a.
Example
input
3
4
2 4 1 3
5
6 9 1 9 6
2
13 37
output
10
12
3
分析
通过画图分析一下，subarray长度为3的时候要中间点比两边大或者比两边小（不能等于），长度为4的时候让其中所有都满足即可。但是再长度是5的时候发现是必定不可能的。
于是我们只需要枚举长度是3或者4的情况判断即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 2000006
#define fi first
#define se second
#define pb push_backint n;
int a[200005];int main()
{
int T = 1;scanf("%d",&T);while(T--){
scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);int ans = n + n - 1;for(int i=2;i<n;i++){
if(a[i] < a[i - 1] && a[i] < a[i + 1] || a[i] > a[i - 1] && a[i] > a[i + 1]) ans++;}for(int i=1;i<=n-3;i++){
if(a[i + 1] > a[i] && a[i + 1] > a[i + 2] && a[i + 2] < a[i + 1] && a[i + 2] < a[i + 3] && a[i + 1] != a[i + 3] && a[i] != a[i + 2] && a[i + 1] > a[i + 3] && a[i + 2] < a[i]|| a[i + 1] < a[i] && a[i + 1] < a[i + 2] && a[i + 2] > a[i + 1] && a[i + 2] > a[i + 3] && a[i + 1] != a[i + 3] && a[i] != a[i + 2] && a[i + 1] < a[i + 3] && a[i + 2] > a[i]) ans++;}printf("%d\n",ans);}return 0;
}