All Tracks Data Structures Stacks Basics of Stacks Problem

Little Shino and Pairs
Tag(s):

Data Structures, Easy, Stack

Problem
Editorial
Analytics

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.

SAMPLE INPUT
5
1 2 3 4 5
SAMPLE OUTPUT
4
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)$$

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

January Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications