till fredrik

gistfile1.txt

import time

def main():
	start = time.time()
	input_data = []	
	while(True):
		try:
			read_input = raw_input()
			if(read_input != ''):
				input_data.append(read_input)
		except EOFError:
			break
	
	input_data = input_data[1:]

	data = [[] for j in xrange(len(input_data) / 2)]
	counter = 0
	for x in range(1,len(input_data),2):
		 days_str = input_data[x].split(' ')
		 days = map(int, days_str)
		 #start = time.time()
		 process(days)
	print 'process time: ' + str(time.time()-start)

def process(prices):
	#print ' '
	total_profit = 0

	inx = range(len(prices))
	inx.sort(lambda x,y: prices[y] - prices[x])

	#print inx

	old_index = -1
	for x in inx:
		if x > old_index:
			#print ' '
		#	print 'x = ' + str(x)
			#print 'old_index=      ' + str(old_index)
			#print 'prices[' + str(old_index) + ':' + str(x+1) + ']   ' + str(prices[old_index:x+1])
			#print str(x+1) + ':end ' + str(prices[x+1:])
			#print prices[old_index:x+1]
			if x - old_index == 1:
				old_index = x
				continue
			total_profit += calculate_profit(prices[:x+1])
	#		print prices
			prices = prices[x+1:]
			old_index = x
			#print ' '
		
	print total_profit

def calculate_profit(prices):
	#print '--- calc profit ---'
	#print prices
	if len(prices) <= 1:
		return 0
	else:
		costs=0
		revenue=0
		for price in prices[:len(prices)-1]:
			costs +=price
		revenue = (len(prices)-1) * prices[-1]
		return revenue-costs


if __name__ == '__main__':
	main()