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

见题面

见题面