시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 3 1 1 33.333%

문제

Given is a sequence of n integers: a1, a2, ..., an. Given is also an integer v. We consider pairs (ai, aj) of elements from the given sequence, such that i < j. 

Write a program count that finds such pair, whose sum ai + aj is the closest to (or the same as) the value of v and output the number of all such pairs with sums ai + aj that are equally closest to the value of v.

입력

On the first line of the standard input, the value of n is written.

On the second line, the values of a1, a2, ..., an, are written, separated by space.

On the third line, the value of v is written.

출력

On the standard output, your program has to print one integer, equal to the wanted count of pairs.

제한

  • 1 < n ≤ 106;
  • −104 ≤ ai ≤ 104 for i = 1, ..., n;
  • −104 ≤ v ≤ 104.

예제 입력 1

9
11 12 8 9 9 2 5 15 16
12

예제 출력 1

4

힌트

The value v = 12 cannot be obtained as a sum of elements of some considered pairs. But 13 can, e.g. 2 + 11=13. So, distance between v = 12 and 13 is 1. There exist some other pairs of elements, which sum is at distance 1 from v = 12. They are: 2 + 9 = 11, 2 + 9 = 11, 5 + 8 = 13. The total number of pairs with sum 11 or 13 is 4. Pay attention that the pair (2, 9) is count twice, because in the given sequence there are two different pairs of elements, although of equal value (2, 9).