HUST Monthly 2010.04.05

From: 2010-04-05 12:00:00 To: 2010-04-05 17:00:00 Now: 2017-09-20 00:58:12 Status: Public

E - Super Chorus

Time Limit: 3s Memory Limit: 128MB

Submissions: 534 Solved: 68
Description
Song is the leader of HUST chorus team. 3 second before a chorus competition he found his team which was already been arranged in a line was out of order, so he decided to eliminate some people to make sure that those m remaining students are bilateral symmetric in height and gender.(The ith person and the (m-i+1)th person have the same height and gender.) The person in the middle was the tallest and the height strictly decreased from the middle to both sides.(If m is a even number ,then the person in the middle refers to the m/2th and (m/2+1)th student.) However, it was too difficult for him so he asked for your help.
Input
Multiple cases, end with EOF. Each case's first line is a positive integer n(0 < n <= 3000) which means the length of the chorus team. n lines followed and each line has two numbers, Hi and Gi. Hi is the height of the ist person.(measured by mm,100<=Hi<=1900) Gi is the gender of the the ist person. Gi=1 means male and Gi=0 means female.
Output
In each case you should output one integer indicating the max number of m.
Sample Input
2
1730 1
1730 1
3
1650 0
1700 1
1650 0
3
1750 0
1670 1
1750 1

Sample Output
2
3
1
Hint
Source
Hust Monthly 10.04.05/xhSong