Equalize Building Heights

Problem Statement

Equalize Building Heights You are given an array Arr of size N where each element Arr i represents the height of a building. You can increase the height of exactly one building in one year, and you have to make all buildings equal by using the following strategy: Choose one building. If the year is odd , the height of the building will increase by 1 . If the year is even , the height of the building will increase by 2 . You can choose no building in any year, and none of the buildings\' height will increase. Find the minimum number of years to make all the buildings the same height. Since the answer can be large, return it mod 10 9 + 7 . Input Format The first line contains an integer N , denoting the number of elements in Arr . Each line i of the N subsequent lines contains an integer describing Arr[i] . Output Format Print the minimum number of years required to make all buildings the same height, modulo 10 9 + 7 . Constraints 1 ≤ N ≤ 10 5 1 ≤ Arr[i] ≤ 10 9 Examples Input: 4 3 5 7 7