Unique Quadruplets Summing to Target

You are given an integer array nums and an integer target. Your task is to find the number of unique quadruplets (i.e. groups of four numbers) in the array that sum up to the given target. Two quadruplets are considered the same if they contain the same set of numbers, regardless of order.

In other words, if the quadruplet [a, b, c, d] sums up to target, any permutation of these four numbers is regarded as the same quadruplet. The expected time complexity is \(O(n^3)\) and the expected space complexity is \(O(1)\) (ignoring the input storage).

inputFormat

The input is read from stdin and consists of three lines:

1. The first line contains an integer n, representing the number of elements in the array.
2. The second line contains n space-separated integers representing the elements of the array nums.
3. The third line contains a single integer representing the target sum.

outputFormat

Output a single integer to stdout representing the number of unique quadruplets that sum up to the given target.## sample

6
1 0 -1 0 -2 2
0

3