N ants are in a circular race. The length of the race is 1000 meters and ant number i is initially Vi meters far from starting point (point 0) of the race in clockwise order. All the ants walk with a speed of 0.1 meters per second, some of them walk in clockwise order, some in counter clockwise order. When two ants meet at a point, they say "Hi" to each other and both of them change their direction of walking to the opposite direction. This process is timeless, meaning they say "Hi" and change their direction in 0 seconds.

You are given the initial position of ants, you don't know their initial directions but you want to know how many times do they say "Hi" to each other after 1000000006 ( 10^9+6 seconds ). You need to find the initial walking direction of ants such that, c1+c2+c3+...+cn is maximized, where ci is the number of times ant number i say "Hi". Print this maximum value.

Input: 

The first line of the input contains an integer N, the number of ants. N is not greater than 100. 

Next line contains n numbers V1 , V2 , ... , VN. All Vi are non negative integers less than 1000. All Vi are distinct.

Output: 

On the only line of the output print an integer being the answer to the test.

Sample Input 

2 

0 500

Sample Output 

400000

Explanation 

In the example there are two ants, In case their direction is the same, they will never say hi to each other, in the other case they will say "Hi" to each other in times 2500, 7500,12500, ... , 999999750. so the result for an Ant would be (999997500 - 2500)/5000+1 = 200000. Hence the answer is 200000*2 = 400000.

Difficulty: MEDIUM
Tags: Number theory

Starter code:

Solutions:
N = int(input())
V = [int(i) for i in input().strip().split()]
V.sort()
noOfLaps = 10 ** 5 * 2
efR = 6
result = 2 * noOfLaps * (N // 2) * (N - N // 2)
pause = 0
for i in range(N - 1):
	if pause != 1:
		if V[i] + 1 == V[i + 1]:
			result += 2
			pause = 1
		else:
			pause = 0
	else:
		pause = 0
print(result)


n = int(input())
nums = [int(i) for i in input().split()]
tot = int(n / 2) * (n - int(n / 2)) * 4 * 10 ** 5
nums.sort()
for i in range(n - 1):
	if nums[i] + 1 == nums[i + 1]:
		tot += 2
		nums[i] = -2
		nums[i + 1] = -2
print(tot)


N = int(input())
pos = sorted([int(i) for i in input().split()])
count = 400000 * (N // 2) * (N - N // 2)
paired = [False] * N
for i in range(N):
	if not paired[i - 1] and (pos[i] - pos[i - 1] + 1000) % 1000 == 1:
		paired[i] = paired[i - 1] = True
		count += 2
print(count)


import sys
TIME = 1000000006
LENGTH = 1000
STEPS = 10
N = int(sys.stdin.readline())
V = sorted(map(int, sys.stdin.readline().split()))
x = TIME // (LENGTH * STEPS) * 4 * (N // 2) * (N // 2 + N % 2)
i = 0
while i < N:
	if V[i] == (V[i - 1] + 1) % LENGTH:
		x += 2
		i += 1
	i += 1
print(x)


import sys
TIME = 1000000006
LENGTH = 1000
STEPS = 10
N = int(sys.stdin.readline())
V = sorted(map(int, sys.stdin.readline().split()))
x = TIME // (LENGTH * STEPS) * 4 * (N // 2) * (N // 2 + N % 2)
i = 0
while i < N:
	if V[i] == (V[i - 1] + 1) % LENGTH:
		x += 2
		i += 1
	i += 1
print(x)


import sys
TIME = 1000000006
LENGTH = 1000
STEPS = 10
N = int(sys.stdin.readline())
V = sorted(map(int, sys.stdin.readline().split()))
x = TIME // (LENGTH * STEPS) * 4 * (N // 2) * (N // 2 + N % 2)
i = 0
while i < N:
	if V[i] == (V[i - 1] + 1) % LENGTH:
		x += 2
		i += 1
	i += 1
print(x)


num_ants = int(input())
hits = num_ants // 2 * (num_ants - num_ants // 2) * 400000
array = sorted(list(map(int, input().split())))
diff = [array[i] - array[i - 1] for i in range(1, num_ants)] + [array[0] + 1000 - array[num_ants - 1]]
start = 0
while diff[start] == 1:
	start += 1
i = start
while i < num_ants:
	if diff[i] == 1:
		hits += 2
		i += 1
	i += 1
i -= num_ants
while i < start:
	if diff[i] == 1:
		hits += 2
		i += 1
	i += 1
print(hits)


import sys
TIME = 1000000006
LENGTH = 1000
STEPS = 10
N = int(sys.stdin.readline())
V = sorted(map(int, sys.stdin.readline().split()))
x = TIME // (LENGTH * STEPS) * 4 * (N // 2) * (N // 2 + N % 2)
i = 0
while i < N:
	if V[i] == (V[i - 1] + 1) % LENGTH:
		x += 2
		i += 1
	i += 1
print(x)


import sys

def solve(a, d, t, v):
	circle_t = int(d / (2 * v))
	circles = t // circle_t
	print('circles=%d' % circles, file=sys.stderr)
	u = len(a) // 2
	v = len(a) - u
	sm = 2 * u * v * circles
	incomplete_circle_t = t % circle_t
	max_distance = int(incomplete_circle_t * 2 * v)
	print('max_distance=%d' % max_distance, file=sys.stderr)
	a.sort()
	i = None
	for (i, t) in enumerate(zip(a, a[1:] + [a[0]])):
		(u, v) = t
		w = v - u
		if w < 0:
			w = d - w
		if w > 1:
			break
	if i is not None:
		a = a[i + 1:] + a[:i + 1]
	print('a=%s' % a, file=sys.stderr)
	ss = set()
	cnt = 0
	for (i, u) in enumerate(a):
		if u in ss:
			continue
		for v in a[i + 1:]:
			if v in ss:
				continue
			w = abs(u - v)
			if w > d // 2:
				w = d - w
			if w == 1:
				cnt += 1
				print('cnt=%d u=%d v=%d' % (cnt, u, v), file=sys.stderr)
				ss.add(v)
				break
		ss.add(u)
	return sm + cnt * 2
_ = int(input())
a = list(map(int, input().split()))
(d, t, v) = (1000, pow(10, 9) + 6, 0.1)
print(solve(a, d, t, v))


input()
x = set(map(int, input().split()))
t = 999
while t in x:
	x.discard(t)
	x.add(t - 1000)
	t -= 1
q = 0
i = min(x)
while i < 1000:
	if i in x:
		chain_length = 0
		while i in x:
			chain_length += 1
			i += 1
		q += chain_length // 2 * 2
	i += 1
l = len(x) // 2
q += l * (len(x) - l) * 2 * 200000
print(q)


n = int(input())
ps = sorted([int(x) for x in input().split()])
res = n // 2 * (n - n // 2) * 4 * 10 ** 5
done = set()
i = 0
while i < len(ps) - 1:
	if ps[i + 1] - ps[i] == 1:
		done.add(i)
		done.add(i + 1)
		res += 2
		i += 1
	i += 1
if 0 in ps and 999 in ps and (0 not in done) and (999 not in done):
	res += 2
print(res)


def main():
	N = int(input())
	V = sorted(map(int, input().split()))
	C = [1]
	for i in range(1, N):
		if V[i] - V[i - 1] == 1:
			C[-1] += 1
		else:
			C.append(1)
	if V[0] + 1000 - V[N - 1] == 1:
		C[0] += C.pop()
	a = N // 2
	b = N - a
	res = 400000 * a * b
	for c in C:
		res += 2 * (c // 2)
	print(res)
main()


n = int(input())
A = sorted([int(x) for x in input().split()])
a = n // 2
b = n - a
rv = a * b * 400000
i = 0
while i < n - 1:
	if A[i] + 1 == A[i + 1]:
		rv += 2
		i += 2
	else:
		i += 1
print(rv)


n = int(input())
l = list(map(int, input().rstrip().split()))
l.sort()
i = 0
j = n
c = 0
while i < j - 1:
	if l[i] + 1 == l[i + 1]:
		c += 2
		i += 2
	else:
		i += 1
k = n // 2 * (n - n // 2) * 4 * 10 ** 5
print(k + c)


n = int(input())
A = sorted([int(x) for x in input().split()])
a = n // 2
b = n - a
rv = a * b * 400000
i = 0
while i < n - 1:
	if A[i] + 1 == A[i + 1]:
		rv += 2
		i += 2
	else:
		i += 1
print(rv)