631. 132 Pattern

0

Medium

Rohan is fond of the **132-pattern**, which is defined as follows:
- A **132 pattern** is a subsequence of three integers nums[i], nums[j], and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].
You are given an array of **n** integers called **nums**.
Determine if there is a 132 pattern in nums and print "True" if it exists, otherwise print "False".

Input Format

The first line contains an integer N, the size of the array.
The second line contains N space-separated integers, representing the elements of the array.

Output Format

Print "True" if a 132 pattern exists, otherwise print "False".

Example

Input

4
3 1 4 2

Output

True

Constraints

1 <= n <= 10^4
-10^4 <= nums[i] <= 10^4

Loading...

View Submissions

Console