BAT3 - BATMAN3


 

"
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


Input

 

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   

 

Output

 

The maximum strength of the army

 

Constraints :

1<=n<=1000

 

 

Example

Input:
1
6 4
6 3 5 2 4 5
Output:
4

hide comments
Romal Thoppilan: 2013-07-09 13:03:13

- Its mentioned in the problem statement: Batman can take his first jump to any of these peaks (and initially he's not standing on any of these peaks).
-He need to the cross the last peak, need not jump on it.

Ujjwal Arora: 2013-07-09 10:36:37

@Romal Thoppilan, is it necessary to choose first peak, or batman could start from any peak ?

for eg.
10 2
6 4 8 7 6 5 4 3 2 1

could batman start from 8 (answer=8) or only from first peak (answer=6) ?

Also, what should we print if batman couldn't reach to the last peak, like :

5 1
6 8 7 3 10

is the answer 2 or 0 ?

Last edit: 2013-07-09 12:17:25
Romal Thoppilan: 2013-03-27 06:30:44

yes!

Witold D³ugosz: 2013-03-18 13:00:59

"(zero based)index of the peak where ROBIN is standing" means, that in the example Robin is on the peek with height 4. So, constraints on m are m>=0 and m<n.
Am I right?

Last edit: 2013-03-18 18:10:00
Romal Thoppilan: 2013-02-16 20:32:49

1. Batman can surely make any kind of jumps forward with the BAT .
2. Nope , the BAT is too heavy to carry along.

Ehor Nechiporenko: 2013-02-12 11:47:39

@Romal Thoppilan, could you please clarify some information. Batman could move strictly down, so he cannot move from height 5 to height 5.
But when he steps to uses mini-Bat, could he make jump to the same height.
And also, when Batman meets mini-Bat, could he use it from another place, or he should jump exactly from the peak m.
As example with input
6 3
6 3 5 2 5 4
Can Batmen take mini-Bat from position 3, then jump to peak 2 and only then use mini-Bat to jump to the peak 5 with height 5?

Ehor Nechiporenko: 2013-02-12 09:50:05

@New AcP:
Starts from 6, then moves to 5 (or 3), then moves to 2 (there is the Robin), then uses mini-BAT and flies to 4 or 5, it doesn't matter.

NeW AcP: 2013-02-09 11:49:04

Can anyone explain me how the output is 4 in the given sample case.
Thanks.


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