Little Josh has found several sticks of various lengths. He wants to form a rectangle with the biggest possible area, using these sticks as the perimeter. He is allowed to glue sticks together, but he is not allowed to break single sticks into multiple shorter sticks. Sticks may only be glued together at their endpoints, so a stick of length 2 and a stick of length 3 can only be glued together to form a stick of length 5.
For example, if Josh has sticks with lengths {1, 3, 3, 4, 5, 7}, he can create a 3 x 5 rectangle using the two sticks of length 3, the stick of length 5, and the sticks of lengths 1 and 4 glued together. This rectangle has an area of 15 square inches, which is the biggest area that can be achieved with these sticks.
You will be given a int[] lengths containing the lengths of the sticks in inches. Return the maximal area (in square inches) of a rectangle that can be created using these sticks. If it is impossible to form a rectangle, return 1.
