Problem: Median of K numbers is defined as the (K/2)th smallest number, if K is even; and the ((K+1)/2)th smallest number if K is odd. For example, 

median of the 4 numbers: 2 1 8 7 is the 2nd smallest number i.e. 2, 

and the median of the 5 numbers:  2 1 8 7 6  is the 3rd smallest number i.e. 6.

In this problem, you'll be given N numbers.  Let the kth median or m(k) be defined as the median of the first k numbers (1 ≤ k ≤ N). i.e. the 5th median or m(5)  is the median of the first 5 numbers, the 8th median or  m(8) is the  median of the first 8 numbers, etc.
In other words, let Ai denote the ith number, then the kth median or m(k) is defined as the median of the numbers A1,A2,…,AK.

Your task is to find m(1) + m(2) + m(3) + ...+ m(n)
Output the answer modulo 100000 (10^5).

INPUT:

There is only one test case. The first line contains N, the count of numbers. N lines follow, each containing one number.

OUTPUT:

Output a single line, containing the sum of the medians.

CONSTRAINTS:

1 ≤ N ≤ 100000

0 ≤ each number Ni ≤ 100000

SAMPLE INPUT
5
10
5
1
2
15

SAMPLE OUTPUT
27

Explanation

m(1)=median of [ 10 ]=10
m(2)=median of [ 10 5 ]=5
m(3)=median of [ 10 5 1 ]=5
m(4)=median of [ 10 5 1 2 ]=2
m(5)=median of [ 10 5 1 2  15 ]=5
( m(1) + m(2) + m(3) + m(4) + m(5) ) % 100000=27

Solution (in PYTHON):

Solution:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'

import heapq
import sys

X = []
N = raw_input()
for i in range(int(N)):
	X.append(int(raw_input()))
#X = [int(l) for l in open(sys.argv[1])]
H_low = []
H_high = []

sum = 0
for x_i in X:
  if len(H_low) > 0:
    if x_i > -H_low[0]:
      heapq.heappush(H_high, x_i)
    else:
      heapq.heappush(H_low, -x_i)
  else:
    heapq.heappush(H_low, -x_i)

  if len(H_low) > len(H_high) + 1:
    heapq.heappush(H_high, -(heapq.heappop(H_low)))
  elif len(H_high) > len(H_low):
    heapq.heappush(H_low, -(heapq.heappop(H_high)))

  sum += -H_low[0]

print sum % 100000