The problem is as follows: Given an array A1,A2....An, the array is called special if there is any Ai which satisfies either of the following cases: 1. Ai is the median of the subarray [A0,Ai-1], or 2. Ai is the median of the subarray [Ai+1,An-1].

If it is special, print 1, else print 0.

Example: Array is 3,6,8,4. This is special because 6 is the median of [8,4].

How to solve this problem?