Company: Infosys SP
Difficulty: medium
HandsOn: Maximum Total Rectangle Area You are given an array A of size N where each element describes the length of the segment you have. You can reduce the length of any segment by one . However, each segment can be reduced only once . It is given that four segments can produce a rectangle. However, a rectangle can be made using four segments AB, BC, CD, DA if and only if AB = CD and BC = DA . Find the maximum total area that can be obtained from the given segments. Since the number can be very large, return it modulo 1e9 + 7 . Note: You don\'t have to maximize the number of rectangles. Input Format The first line contains an integer, N , denoting the number of elements in A . Each line i of the N subsequent lines (where 0 ≤ i < N ) contains an integer describing A[i] . Output Format Print a single integer — the maximum total area that can be obtained, modulo 1e9 + 7 . Constraints 1 ≤ N ≤ 10 5 1 ≤ A[i] ≤ 10 5 Examples Case 1 Input: 4 2 4 2 5 Output: 8 Here, N=4 and A=[2,4,2,5]. We