519. Pattern in an Array

0

Medium

Rahul has been given an array, arr, consisting of n integers. His task is to determine whether there exists a pattern in the array. A pattern is defined as a subsequence of three integers, arr[i], arr[j], and arr[k], where i < j < k and arr[i] < arr[k] < arr[j].

Input Format

The first line of input contains the size of the array, n. The second line contains n space-separated integers, representing the elements of the array.

Output Format

Print 'true' if a pattern exists in the array, otherwise print 'false'.

Example

Input

4
1 2 3 4

Output

false

Constraints

n is equal to the length of the array, arr. The value of n must be between 1 and 200,000, inclusive. Each element in arr must be between -1,000,000,000 and 1,000,000,000, inclusive.

Loading...

View Submissions

Console