Adam, our ancestor, was on his way to Eve with “the” apple. On the way he saw ‘N’ trees located on a straight line in a jungle with heights H1, H2, H3...… HN respectively. Two monkeys A and B are sitting on trees Ta and Tb (1 <= a < b <= N) respectively. A will always be on the tree with smaller index than of B. To get passed Adam has to offer them “the” apple. Monkeys will accept "the" apple, split it in two halves and let Adam go if they have seen each other on trees, otherwise they will start fighting for apple and Adam can run away with apple as they are busy fighting.
Two monkeys can see each other only if there is no tree Tk in between Ta and Tb(a < k < b) such that its height Hk is higher than any of Ta and Tb. Technically speaking monkeys cannot see each other if Hk>Ha or Hk>Hb(let’s not go with the fundamentals of Maths for this question).
Your task is to tell in how many possible situations Adam would be able to run away with “the” apple and make the legend happen :)
6
4
3
5
2
2
5
Output:
6
Explanation:
6 trees with heights (4,3,5,2,2,5) respectively. In 6 situations Monkeys won’t see each other.
(Ta, Tb) = (1, 4) (1, 5) (1, 6) (2, 4) (2, 5) (2, 6) corresponding (Ha, Hb) would be (4,2) (4,2) (4,5) (3,2) (3,2) (3,5)