Any suggestions to improve the performance of the following code? This code is exceeding the time limit for the last four cases. This is a solution to the problem https://www.interviewstreet.com/challenges/dashboard/#problem/4fcf919f11817
def main():
N = int(raw_input())
if(0<=N<=100000):
x = []
ans=[]
l=[]
m=[]
for i in xrange(0, N):
tmp = raw_input()
a, b = [xx for xx in tmp.split(' ')]
l.append(a)
m.append(int(b))
for i in xrange(0, N):
if l[i]=='r':
if len(x)<1 or m[i] not in x:
ans.append('Wrong!')
elif m[i] in x:
x.remove(m[i])
q=len(x)
if q%2==1:
ans.append(x[(q/2)])
elif q%2==0:
if q==0:
ans.append('Wrong!')
else:
k=x[q/2]+x[(q/2)-1]
if k%2==0:
ans.append(int(k)/2)
else:
ans.append(k/2.0)
elif l[i]=='a':
x.append(m[i])
x=sorted(x)
p=len(x)
if p%2==1:
ans.append(x[(p/2)])
else:
k=x[p/2]+x[(p/2)-1]
if k%2==0:
ans.append(int(k)/2)
else:
ans.append(k/2.0)
for i in ans:
print i
if __name__ == "__main__":
main()
from sys import stdin,stdout
from bisect import bisect,insort
def main():
N = int(raw_input())
x = []
ans = []
append = x.append
ans_append = ans.append
remove = x.remove
read = stdin.readline
for i in xrange(0, N):
tmp = read()
a, b = tmp.split(' ')
b = int(b)
if a == 'r':
search_result = search(x,b)
if len(x) < 1 or not(search_result):
ans_append('Wrong!')
else:
remove(b)
ans_append(median(x))
else:
insort(x, b)
ans_append(median(x))
for i in ans:
print i
def median(arr):
q = len(arr)
if q==0:
return 'Wrong!'
if q%2 == 1:
return arr[(q/2)]
else:
k = arr[q/2] + arr[(q/2)-1]
if k%2 == 0:
return int(k)/2
else:
return k/2.0
def search(arr,element):
position = bisect(arr, element)
if len(arr) >= position and len(arr)!=0:
if arr[position-1] == element:
return True
else:
return False
else:
return False
if __name__ == "__main__":
main()