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