Bruce Wayne: I do fear death. I fear dying in here while my city burns. 
Blind Prisoner: Then make the climb.
Bruce Wayne: How?
Blind Prisoner: As the child did. Without the rope. Then fear will find you again.


" Bruce Wayne: I do fear death. I fear dying in here while my city burns.
 Blind Prisoner: Then make the climb.
 Bruce Wayne: How?
 Blind Prisoner: As the child did. Without the rope. Then fear will find you again. "


The Epic fight between BANE and BATMAN saw BATMAN on the losing side .Bane delivers a crippling blow to Batman's back, then takes him to a foreign, well-like prison where escape is virtually impossible .

The prison as we know is a place from where no man ever escaped , except for the child of Ra's al Ghul himself . 

The heroics of BATMAN saw him escape the prison , however after the prison came the Valleys . To reach the city , He needed to cross these valleys . Meanwhile , BANE's army has surrounded the city and trapped all the policemen underground . Each of these peaks contain exactly one policeman held captive by Bane's men. Since, BATMAN needs to build his own army , he decides to free some of the policemen on his way . 

Also BATMAN needed to save his energy before his battle with Bane ,so he decided to take only downhill (strictly) jumps .Detective John Blake ( now called as ROBIN ) is standing in one of these peaks with a mini-BAT . This will allow BATMAN to take a maximum one jump uphill ahead . BATMAN can choose to flee ROBIN and use the BAT or rather cross over without his help .

The task in hand is to maximize the army strength to face BANE as BATMAN crosses over.
(BATMAN can take his first jump on any of these peaks)


" Bane : So, you came back to die with your city. 
   Batman : No. I came back to stop you



t , number of testcases
n : number of peaks ,  m : (zero based)index of the peak where ROBIN is standing
n intergers denoting the height of the peaks   




The maximum strength of the army


Constraints :





6 4
6 3 5 2 4 5

hide comments
kumar_anubhav: 2020-08-17 12:42:28

means after reaching to mth index batman can explore all other hill ? if not then what exactly we have to do??

kushrike: 2020-05-09 23:20:34

he can only jump from m'th peak to any peak of his wish that lies from m+1 to n.
Simple LIS implementation...take both cases
1. Longest subsequence
2. Longest sequence upto m'th index + Longest sequence after m'th index + 1

amansahu112: 2020-05-08 19:25:30

if he uses mini-bat then he can jump to any peak from m+1 till n

abhinav_99: 2019-10-28 13:05:42

Same as longest increasing subsequence just reverse the condition and skip the comparison at the mth index.

rishabh_jiit: 2019-07-06 10:47:16

Guys please skip this problem it has the worst problem statement .

god_coder: 2019-05-30 14:09:48

Very poor description of the problem. Extremely unclear statement

spectre009: 2019-01-04 11:01:32

Very poor description, first of all bat can only be used at m and it is not important that Batman should start from 0 index.

aman_sachin200: 2018-06-13 09:41:01

Nice one!!!Remember that BATMAN can use the BAT only on the peak where ROBIN is standing!!!!Cost me 1 WA :(

codiesam_007: 2018-05-17 22:37:56

weak tc:
10 5
9 8 7 6 5 4 3 2 5 1
ans : 9 not 8 but still it passes

sherlock11: 2018-02-11 08:28:45

make sure that array is 0 index,,,,,,,,,,,,,costed me 2 wa

Added by:Romal Thoppilan
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem