All Tracks Data Structures Stacks Basics of Stacks Problem

Monk and Prisoner of Azkaban
Tag(s):

Data Structures, Easy, Stack

Problem
Editorial
Analytics

Monk's wizard friend Harry Potter is excited to see his Dad fight Dementors and rescue him and his Godfather Sirius Black. Meanwhile their friend Hermoine is stuck on some silly arrays problem. Harry does not have time for all this, so he asked Monk to solve that problem for Hermoine, so that they can go.

The problem is given an array $$A$$ having $$N$$ integers, for each $$i \; (1 \le i \le N)$$, find $$x+y$$, where $$x$$ is the largest number less than $$i$$ such that $$A[x] > A[i]$$ and $$y$$ is the smallest number greater than $$i$$ such that $$A[y] > A[i]$$. If there is no $$x < i$$ such that $$A[x] > A[i]$$, then take $$x=-1$$. Similarly, if there is no $$y > i$$ such that $$A[y] > A[i]$$, then take $$y=-1$$.

enter image description here

Input Format:
First line consists of a single integer denoting $$N$$.
Second line consists of $$N$$ space separated integers denoting the array $$A$$.

Output Format:
Print $$N$$ space separated integers, denoting $$x+y$$ for each $$i \; (1 \le i \le N)$$

Constraints:
$$1 \le N \le 10^6$$
$$1 \le A[i] \le 10^{18}$$

SAMPLE INPUT
5
5 4 1 3 2
SAMPLE OUTPUT
-2 0 6 1 3 
Explanation

Values of $$x$$ for each $$i$$: $$-1, \; 1, \; 2, \; 2, \; 4$$
Values of $$y$$ for each $$i$$: $$ -1, \; -1, \; 4, \; -1, \; -1$$
So, $$x+y$$ for each $$i$$: $$-2, \; 0, \; 6, \; 1, \; 3$$

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

CodeMonk (Stacks & Queues)

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications