Given an array, your goal is to find, for each element, the largest subarray containing it whose cost is at least .
Specifically, let be an array of length , and let be the subarray from index to index . Also,
- Let be the largest number in .
- Let be the smallest number in .
- Let be the bitwise OR of the elements of .
- Let be the bitwise AND of the elements of .
The cost of , denoted , is defined as
You are given the array and and an integer . For each index from to , your goal is to find the largest size of any subarray such that and .
Consider, array and . The possible sub-arrays and their costs would be as follows:
Complete the function costlyIntervals
which takes two integers and as first line of input, and array in the second line of input. Return an array of integers, where the element contains the answer for index of the input array, . Every element of the output array denotes the largest size of a subarray containing whose cost is at least , or if there is no such subarray.
Constraints
Subtasks
- For of the maximum score, .
- For of the maximum score, .
Sample Input
,
Sample Output
Explanation
In this example, we have . There is only one subarray whose cost is at least , and that is , since . Its size is . Thus, for and , the answer is , and for the others, .