A markets analyst logs the price of a single stock at n evenly spaced ticks during one trading session. A session is called a peak-valley-recovery session if the logged prices can be split into three consecutive, non-empty stretches: an opening rally that strictly climbs up to some tick p (the session's peak), a sell-off that strictly falls from tick p down to some later tick q (the session's trough), and a closing rally that strictly climbs from tick q all the way to the final tick.

Formally, the session qualifies if there exist indices 0 <= p < q <= n - 1 such that:

• prices[0] < prices[1] < ... < prices[p]
• prices[p] > prices[p+1] > ... > prices[q]
• prices[q] < prices[q+1] < ... < prices[n-1]

A stretch that covers only a single index is automatically valid, since it contains no adjacent pair to compare. Given the logged prices, decide whether the session qualifies.

Input format

• Line 1: a single integer n — the number of logged ticks (3 <= n <= 100000).
• Line 2: n space-separated integers prices[0], prices[1], ..., prices[n-1] (1 <= prices[i] <= 10^9).

Output format

Print true if the session is a peak-valley-recovery session, or false otherwise.

Constraints

• 3 <= n <= 100000
• 1 <= prices[i] <= 10^9
• Every comparison in a stretch must be strict; two consecutive ticks with an equal price break any stretch they both belong to.

7
1 3 5 4 2 3 6

true

4
2 4 6 8

false