Split Array into Strictly Increasing and Decreasing Subsequences

Problem Statement:

You are given an array of integers. Your task is to determine whether it is possible to split the array into two non-empty contiguous parts such that one part is strictly increasing and the other part is strictly decreasing.

Formally, given an array \(a_1, a_2, \dots, a_n\), find an index \(i\) (where \(1 \le i < n\)) such that either:

• \(a_1 < a_2 < \dots a_{i+1} > \dots > a_n\),
• or \(a_1 > a_2 > \dots > a_i\) and \(a_i < a_{i+1} < \dots < a_n\).

Note that a sequence with a single element is considered both strictly increasing and strictly decreasing. Output 1 if such a split exists, otherwise output 0.

inputFormat

The input begins with an integer \(T\) (the number of test cases). Each test case is described as follows:

• The first line contains an integer \(n\) (the number of elements in the array).
• The second line contains \(n\) space-separated integers.

Input is read from stdin.

outputFormat

For each test case, output a single line containing 1 if the array can be split into one strictly increasing and one strictly decreasing subsequence, or 0 otherwise. Output is written to stdout.

## sample

3
5
1 2 3 4 5
6
5 3 2 1 4 6
4
1 3 2 4

1
1
0

</p>