This was a difficult puzzle. I had trouble understanding the answer even when it was given to me, and had to go to Alok Mittal for rescue. Siddharth Goel (Founder, Adstrak) gave some useful links for this puzzle and Sumar Saraf was the only one to give the right answer, though with a bit of brute force and not the actual proof.

I am reproducing the answer sent to me by Alok Mittal.

Mark every person by two numbers – the max number of consecutive ascending chain that ends at him or her, and max descending chain that again ends at him or her (beginning from the left). No two people can have same (asc,des) pair – the reason being that both have different heights. If the one standing on the right has a smaller height then the des # for the right one will at least be one higher than the one standing on the left and vice versa for the asc number in case the right one is taller. We also know that the minimum number for sac or des needs to be at least 1. Hence with 10 people, someone must have a “4” in at least one of ascending or descending tag.

In general, for numbers between n^2+1 to (n+1)^2, the minimum will be n+1.

A more general treatment of the problem is available on Wikipedia at the following link:

https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem

Hope you enjoyed the puzzle!