Each archer's dragon moves right and eats peaks lower than its start until it meets a taller peak; find the largest count any archer can eat.
Medium5StackArrayImplementationGreedyInterviewNo attempts yetTime limit2sMemory limit256 MB"Greetings. My name is Bangogh, the finest archer in the land. Today again I take aim at my enemies from a peak of Geumgangsan. Not one enemy standing before me gets away. Good, the lunar eclipse is about to begin. Once it begins, my dragon will swallow them whole. Watch the skill of Bangogh, the archer of Majang-dong!"
Bangogh has no idea that Deonggi is standing on the peak behind him. Just like Bangogh, Deonggi plans to call out a dragon when the eclipse begins and wipe out every other archer in front of him. In fact, it is not only those two: every archer on the N peaks of the Geumgang Range has the same plan.
The Geumgang Range has N peaks in total, and one archer stands on each peak waiting for the eclipse to start. Food has become plentiful in the heavens, though, so the dragons have grown fat. A dragon can only kill enemies standing on peaks lower than the peak it started from. A dragon that meets a peak higher than its starting peak gives up the attack on the spot, lies down at the foot of the mountain, and takes a nap. All peak heights are different, and every dragon travels to the right only. No dragon turns around along the way, and no peak collapses or rises up.
"A shadow has fallen over the moon."
The eclipse has begun. Which of these archers is the best? Find the largest number of enemies a single archer can kill.
The first line contains N, the number of peaks and also the number of archers. (1≤N≤30,000)
The second line contains the heights of the N peaks in order from the leftmost peak. (1≤ height ≤100,000) The heights are all distinct, with no duplicates.
Print the largest number of enemies the best archer can kill, on one line.
In the first example the archer on the peak of height 10 kills the archers on the peaks of height 2, 5, and 7. The dragon travelling right then meets the peak of height 11 and gives up the attack.