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

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++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...

Contributor

This Problem was Asked in

Challenge Name

January Circuits '17

All Tracks Data Structures Stacks Basics of Stacks Problem

Data Structures, Easy, Stack

CODE EDITOR

Contributor

This Problem was Asked in

Social Share