Count The Triplets

View as PDF

Submit solution

Points: 7
Time limit: 0.6s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Given an array of N integers, the task is to count all the triplets such that sum of two elements equal the third element. When counting triplets, only count the unique ones. A unique triplet is when all three numbers of the triplet put in increasing order are unique, for example, the triples 1 2 3 and 3 2 1 are not unique, but the triplets 8 5 3 and 8 4 4 are unique. The triplets themselves do not necessarily have to be unique, this means that 8 4 4 can be possible, as long as the 2 4s do not have the same index.

Input

The first line of input contains N, denoting the size of the array.

The second line of the input contains N space separated elements A_i, the elements of the array.

Output

Output the number of unique triplets in the array, if there are no such triplets, output -1.

Constraints

3 \le N \le 5000

1 \le A_i \le 10^6

Sample Input 1

4
1 5 3 2

Sample Output 1

2

Explanation Of Sample 1

There are 2 such triplets, 1, 2, 3 and 2, 3, 5.

Sample Input 2

3
3 2 7

Sample Output 2

-1

Comments


  • 5
    Togohogo1  commented on Dec. 31, 2019, 1:18 p.m.

    Hints to not TLE with PY3?


    • 4
      Togohogo2  commented on Jan. 19, 2020, 12:10 p.m. edited

      Don't use PY3 and learn basic math.


  • -1
    c  commented on July 24, 2019, 5:49 p.m.

    Is the test data wrong or is everyone just bad?


    • 2
      magicalsoup  commented on July 24, 2019, 6:18 p.m.

      I'll have to check the test-data