Little Shino and Pairs

★★★★★

3.9

90 votes

Approved, Data Structures, Easy, Stacks

Details

Submissions

Discussion

Editorial

Problem

Given a permutation of number from 1 to N. Among all the subarrays, find the number of unique pairs $(a, b)$ such that $a \neq b$ and a is maximum and b is second maximum in that subarray.

Input:
First line contains an integer, N $(1 \le N \le 10^5)$ . Second line contains N space separated distinct integers, $A_i$ $(1 \le A_i \le N)$ , denoting the permutation.

Output:
Print the required answer.

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

All the possible subarrays are:

1
$1\; 2$
$1\; 2\; 3$
$1\; 2\; 3\; 4$
$1\; 2\; 3\; 4\; 5$
2
$2\; 3$
$2\; 3\; 4$
$2\; 3\; 4\; 5$
3
$3\; 4$
$3\; 4\; 5$
4
$4\; 5$
5

The 4 unique pairs are:
$(2,\; 1)$
$(3,\; 2)$
$(4,\; 3)$
$(5,\; 4)$