I'm pretty new to CodeForces and I recently participated in my first contest. I code in python and I kept having problems with performance issues (my solutions were too slow).

For problem 381B I changed the code and resubmitted it and now it was fast enough but I was wondering why my first solution was so slow? How can I make programs faster in python / Which functions and methods are slow?

First (slow) code:

M = int(raw_input())
up = []
down = []

for i in map(int, raw_input().split()):
    if i not in down:
        down.append(i)
    else:
        up.append(i)

down.sort(reverse=True)
up.sort()

if len(up) > 0 and down[0] == up[-1]:
    del up[-1]

up.extend(down)

print len(up)
print ' '.join(map(str,up))

Second (fast) code:

M = int(raw_input())
cards = map(int, raw_input().split())
cards.sort()

stair = [cards.pop(-1)]
index = len(cards) - 1
prevDown = stair[0]
prevUp = stair[0]

while index >= 0:
    if cards[index] != prevDown:
        prevDown = cards[index]
        stair.append(cards.pop(index))
        index -= 1
    elif cards[index] != prevUp:
        prevUp = cards[index]
        stair.insert(0,cards.pop(index))
        index -= 1
    else:
        index -= 1

print len(stair)    
print ' '.join(map(str, stair))