TIOJ 1017 . C.Node of Sequence

O(N)

#include<cstdio>
#include<cstdlib>
int arr[1000005];
bool ch1[1000005];
bool ch2[1000005];
int main(){
    int T;scanf("%d", &T);while(T--){
        int a;scanf("%d", &a);
        for(int lx = 0;lx < a;lx++) scanf("%d", arr+lx);
        int mm1 = arr[0], mm2 = arr[a-1];
        for(int lx = 1;lx < a;lx++){
            ch1[lx] = arr[lx] > mm1;
            if(arr[lx] > mm1) mm1 = arr[lx];
        }
        for(int lx = a-2;lx >= 0;lx--){
            ch2[lx] = arr[lx] < mm2;
            if(arr[lx] < mm2) mm2 = arr[lx];
        }
        int mao = 0;
        for(int lx = 1; lx < a-1;lx++)
            mao += ch1[lx] and ch2[lx];
        printf("%d\n", mao);
    }
    return 0;
}