**Problem link** : Richie’s Mountain

**Contest** : RECode 9.0

**Author** : Abhishek

**Tester** : Shivansh

**Editorialist** : Abhishek

**Difficulty** : Easy

**Prerequisites** : Basic DP

**Problem** : You are given the height of a mountain at n points. Given m queries

having two integers l , r , find whether the range (l,r) has exactly one peak.

A range consisting of a peak will look like a_i < a_{i+1} < a_{i+2} ..... < a_{x} > a_{x+1} > a_{x+2} .... > a_{j} . (i≤x≤j)

**Explanation** : Simple DP approach.

Maintain two arrays left and right. Left[i] denotes the number of integers which form an continuous strictly increasing sequence starting from Arr[i] and right[i] denotes the number integers which form a continuous strictly decreasing sequence ending at Arr[i].

For a given query (l , r), we have the values of both, the length of increasing sequence from arr[l] and the length of decreasing sequence ending at arr[r]. Adding the length of increasing and decreasing sequence starting at l and ending at r respectively should be greater than or equal to length of the interval +1(as the top most point or the peak will be counted twice, both for increasing and decreasing sequence), i.e. (r-l+1)+1.

**Time Complexity** : O(n)

**Setter’s Solution** : Solution