THEATRE - Movie Theatre Madness


A group of friends have gone to watch the first day first show of an awesome new movie. However, since they did not book the tickets well in advance, they have ended up with crazy seats. To be more specific, rather than getting seats such that all the friends are seated in the same row, they have ended up with seats such that all of them are seated in the same column! Now this is very inconvenient since they won't be able to chat with each other during the movie or have any kind of fun, but they are okay with this since they'd rather watch the movie like this, than not watch the movie at all.

But there is another problem apart from this. Now we know that all the friends are seated in a single column, one behind the other. Since all of them reached the theatre just in time for the movie, they rushed and occupied the first of the booked seats that they could find. However all the friends have different heights, and due to the lack of planning, there is no guarantee that a shorter person is always seated in front of a taller person. But this would mean that the shorter person would struggle to see the screen throughout the movie!

But the movie has started and it's too late now to do anything.

What you need to do is the following: For every person, find the height of the closest person seated in front of him/her who is blocking his/her view (that is, the person closest in front with a greater height). If no such person exists, take this height as 1. Print the product of all such values modulo 1000000007.

Input

On the first line you have a single integer N (2 <= N <= 105), the total number of friends.

This is followed by N space separated integers a1, a2, ... aN, which correspond to the height of the people from back to front. That is, a1 is the height of the person seated on the last row, a2 is the height of the person seated on the second last row (just in front of a1) and so on, up to aN which is the height of the person seated right at the very front (1 <= ai <= 109). Note that all these integers are distinct.

Output

On a single line, output the result. (For every person, find the height of the closest blocking person. This value is 1 if no such person exists. Print the product of all these values modulo 1000000007).

NOTE: By closest blocking person to ai we mean find aj, such that aj > ai, j > i, and (j-i) is minimum. (Please look at sample test cases for further clarity.)

Example

Input #1:
5
5 2 1 4 3
 
Output #1:
16
Input #2:
5
9 8 3 5 7

Output #2:
35
Input #3:
10
30 10 50 70 11 60 20 80 31 12

Output #3:
999962375

Explanation

Input #1:

  • blockingHeight(5) = 1 (since 5 is the tallest, no one is blocking him)
  • blockingHeight(2) = 4
  • blockingHeight(1) = 4 (although 3 is also taller that 1, 4 is closer to 1)
  • blockingHeight(4) = 1 (No one blocking 4)
  • blockingHeight(3) = 1 (No one blocking 3)
  • Answer=1*4*4*1*1=16

hide comments
Kid Algorist: 2014-10-25 13:35:19

DP like approach gives 0.27s AC.
5
100000 10000 1000 100 1000000
o/p
49000000

The Arrow: 2014-09-01 20:36:51

@green
O(n^2) solution will not work. Do it in O(n).Think upon it.

@nirvit
blockingHeight( 30 ) = 50
blockingHeight( 10 ) = 50
blockingHeight( 50 ) = 70
blockingHeight( 70 ) = 80
blockingHeight( 11 ) = 60
blockingHeight( 60 ) = 80
blockingHeight( 20 ) = 80
blockingHeight( 80 ) = 1 (no one on the right of 80 is taller than 80)
blockingHeight( 31 ) = 1 (no one on the right of 31 is taller than 31)
blockingHeight( 12 ) = 1 (no one on the right of 12 is taller than 12)
so
Answer=(50*50*70*80*60*80*80*1*1*1)%1000000007
Note: Do mod after each multiplication instead of doing it at last.

Last edit: 2014-09-01 20:38:05
Nirvit Rustagi: 2014-07-08 11:50:34

can anyone explain the third test case.?

ggkjh: 2014-07-01 20:40:21

my o(n^2) algo is giving tle...any sort of hint is appreciated..:)

785227: 2014-06-06 11:25:29

Cool question :)

Deepak gupta: 2013-12-21 21:23:58

Easy one !! AC in one go :)

codecode: 2013-10-20 11:39:39

plz anyone provide difficult test case here so that i can check my code

codecode: 2013-10-20 11:35:16

i am getting correct answer for any possible test cases dont know why i am getting wrong answer...i am sure that my code is correct

innovolt: 2013-10-20 10:57:02

simple ques. AC at first go...thanx to my O(n) algo

Last edit: 2013-10-20 10:59:44
Aayush Agarwal: 2013-10-16 23:16:54

Nice Question :)


Added by:Gowri Sundaram
Date:2013-03-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET