Cah the rat, being so stupid, didn't do too well for his N (0 < N < 100000) exams. That's not very good news as his mother would beat him if his median score is less than 50, that means that if we sort his scores, he would be beaten if Scores[ceiling((N - 1)/2)] < 50. However, his mother can only see his scores online in a nice little column, as monitors for rats are pretty small, there is a limited number of scores Cah's mother can see at once (at least 1 and not more than N). Due to her age, she calculates the median based only on the scores she can see after scrolling to a random position on the website.

Hence there are a number of scenarios that could happen, for example his mother could be using a 3 line monitor and starting to read from the first line, or using a 6 line monitor and starting to read from the second line. However, she will try to maximise the use of monitor space by ensuring that the whole screen is used.

Help Cah determine the number of unique scenarios where he would be beaten.

Input

The first line of input will contain N, the number of exams.

The following N lines will contain the score of each exam which will be between 0 and 100 inclusive.

Output

The number of scenarios that will lead to Cah being beaten.

Sample Input

5
1
30
50
20
70

Sample Output

8

Explanation

1, 30, 20, (1, 30), (1, 30, 50), (30, 50, 20), (1, 30, 50, 20), (1, 30, 50, 20, 70)