Question # 2 (Proper solution Required)

An array of n integers x1, x2, . . . , xn is known to have the following property: elements follow in ascending order up to a certain index p where 1 < p < n, then there are several equal entries up to a certain index q, where p < q < n and then follow in descending order: x1 < x2 < . . . < xp1 < xp = xp+1 . . . = xq > xq+1 > . . . > xn. Give an efficient algorithm to find the indices p and q. Note: the worst case running time of your algorithm must be in o(n), so simple scanning from left to right will get 0 marks. Detailed pseudocode along with the brief description of main idea and justification of correctness is required for full mark in this question.