479. Triplet Existence

0

Medium

Given an array of integers, Sam needs to determine if there exists a triplet (i, j, k) that satisfies the following conditions:

1.

1.

**i < j < k 2.****a[i] < a[k] < a[j].**If both conditions are met, output 1; otherwise, output 0.Input Format

The first line of input contains the length of the array.
The second line of input contains the elements of the array separated by spaces.

Output Format

Output a single digit, either 0 or 1.

Example

Input

4
1 2 3 4

Output

0

Constraints

1 <= n <= 2 * 10^5

-10^9 <= nums[i] <= 10^9

-10^9 <= nums[i] <= 10^9

Loading...

View Submissions

Console