Good Numbers

Interview

Time limit2sMemory limit256 MB

Summary
Given N integers, count how many of them equal the sum of two other numbers at two different positions in the sequence.
Level

Medium5 of 10

Topics
Two pointers, Array, Hash map
Solved
No attempts yet

Problem

You are given N integers. A number at one position is called a good number if it can be represented as the sum of two numbers from two other distinct positions.

Even when two values are equal, they are considered different numbers if they are at different positions. Determine how many numbers in the sequence are good.

Input

The first line contains the number of integers N (1 ≤ N ≤ 2,000).

The second line contains N integers A_i. Each integer satisfies |A_i| ≤ 1,000,000,000.

Output

Print the number of good numbers on one line.

Hint

If the sequence is 1 through 10, then 3, 4, 5, 6, 7, 8, 9, and 10 are good numbers.

Examples1

  1. Example 1

    Input
    10
1 2 3 4 5 6 7 8 9 10
    Expected output
    8