Cats are usually involved in cat fights, and Rar the Cat is no exception. However, Rar the Cat has only P 'battle power' and each other cat has also their respective 'battle powers' as well.
When two cats fight, their 'battle power' deceases by the same amount until one of their battle power reaches zero. Eg: If cat A with battle power 5 fights with cat B with battle power 6, after the battle, cat A would be left with 0 battle power (unable to fight anymore) and cat B would be left with battle power 1. In this case, we say that cat B has defeated cat A. In the event that two cats have the same 'battle power', both of the cats are considered to have lost the battle.
Rar the cat has been challenged to defeat as many other cats as possible. However, he must pick contiguous segments from a line of N cats to defeat, meaning that the cats he pick to fight with must be in consecutive order. In order to consider Rar the Cat to have 'defeated' a group of cats, he must be able to defeat all of them. Do note that his battle power does not 'recover' at all in this scenario.
Your task, is to count the number of cats inside the largest group of consecutive ordered cats Rar the Cat can defeat.
The first line of input consists of 2 integers, N and P.
The following line of input consists of N integers, with the ith integer being the 'battle power' of the ith cat.
A single integer, the number of cats inside the largest group of consecutive ordered cats Rar the Cat can defeat.
The 'battle powers' of any cat (including Rar the Cat) will always be strictly positive and also fit inside a 32-bit signed integer.
Subtask 1 (27%): N = 200.
Subtask 2 (31%): N = 3000.
Subtask 3 (42%): N = 1000000.
Subtask 4 (0%): Sample Testcases
Input:
10 20 9 8 2 3 7 2 4 8 5 6
Output:
5
Explanation:
By selecting cats with 'battle power' [2 3 7 2 4] to defeat, Rar the Cat would be able to defeat all of them and have 2 'battle power' remaining. This is the largest group of consecutive ordered cats Rar the Cat can defeat.
Input:
10 1 9 8 2 3 7 2 4 8 5 6
Output:
0
Explanation:
Rar the cat cannot defeat any cat.
| Subtask | Score |
|---|---|
| 1 | 27 |
| 2 | 31 |
| 3 | 42 |
| 4 | 0 |