663. Number of Visible Pairs in a Queue

People with distinct heights stand in a line. Two people at positions i < j can see each other if every person strictly between them is shorter than both. Return the total number of visible pairs. The input is JSON {heights}.

Input: JSON {heights}.

Output: Integer — the number of visible pairs.

Examples

Input: {"heights":[10,6,8,5,11,9]}
Output: 8
Explanation: There are 8 mutually visible pairs.

Input: {"heights":[5,1,2,3,10]}
Output: 7
Explanation: Five visible pairs.

Input: {"heights":[7]}
Output: 0
Explanation: No pair.

Constraints

• 0<=n<=10^5
• distinct heights

Asked by