Given an unsorted array of n integers numbers (with possible duplicates) in range [1..k] Implement in Java an algorithm that preprocesses the input array in O(n+k) running time and then returns how many integer numbers there are in the range [left..right] in o(1) running time for any given left and right, 1 s left s right s k. Example: Input: int [ ] a = {3, 8, 2, 4, 1, 9, 11, 4, 15); //input array int k = 15; int left = 2; int right = 9; Output: Total number in range [2..9] is 6 // max element in a // lower value in range // upper value in range