13526 - Enmingw's Recyclables Depot   

Description

Electric Mingw is a handsome and electric rich man. Nevertheless, he has a weird hobby to collect resources in his own recyclables depot which is located at the upstream of Golden River, containing items ranging from golden tiolet to recyclable plastic.

Since the recycled resources he collected are too many, Enmingw decides to hold an auction of recycled resources, offering various combanations.

Your task is to compute the number of pairs of recycled resources whose sum of values is equal to \(V\).

Note

TL; DR

What's the difference between set/map and unordered_set/map? Overall, their behaviors are alike. We could deem them as the same Abstract Data Types (ADT) implemented in different approaches. set/map are based on Red-Black Tree (a self-balanced Binary Search Tree), while unordered_set/map are hash tables. In fact, they're declared by polymorphism in Java, a more Object-Oriented language.

A balanced BST could perform insertion and deletion in \(O(\log N)\) even despite of the worst case, whereas a hash table has a average \(O(1)\) time complexity in amortized analysis yet decline to \(O(N)\) when collision, i.e., different keys have the same hash value, occurred.


Though hash tables are faster than BSTs in the most cases, it's easy to construct test cases which lead to many collisions, if we know the hash function the hash table used. So everytime you use unordered_set/map, be care of this pitfall.

So how to avoid this? We could use other hash tables and custom hash function (random and/or time-dependent argument), or simply use set/map alternatively.

Input

There is an integer \(N\) in the first line, indicating the number of recycled resources to be auctioned.

The next line contains \(N\) integers \(a_i\), representing the values of each recycled resource.

The test case is ended by an integer \(V\) mentioned above.

\[1\leq N\leq10^6,0\leq a_i\leq10^6,-2^{31}\leq V<2^{31}\]

Output

For \(V\), please print out an integer which is the number of \((i, j)\) such that \(i<j\land a_i+a_j=V\).

Remember to put a new line character at the end.

Sample Input  Download

Sample Output  Download

Tags




Discuss