Three Sum Closest

Given an integer array nums of length n and an integer target, find three integers in nums whose sum is closest to the target. Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Note: The answer is not necessarily the closest to zero but the closest to target.

Mathematical Formulation:

Given a set \( S = \{a_1, a_2, \ldots, a_n\} \) and a target \( T \), find three indices \( i, j, k \) (with \( i < j < k \)) such that the value \( |a_i + a_j + a_k - T| \) is minimized.

inputFormat

The first line contains an integer n, representing the number of elements in the array.

The second line contains n space-separated integers, representing the elements of the array.

The third line contains an integer target, which is the target value.

Input is read from standard input (stdin).

outputFormat

Output a single integer: the sum of three numbers in the array that is closest to target. Output is written to standard output (stdout).

## sample

4
-1 2 1 -4
1

2

</p>