CF1514D Cut and Stick

Baby Ehab has a piece of Cut and Stick with an array $ a $ of length $ n $ written on it. He plans to grab a pair of scissors and do the following to it: - pick a range $ (l, r) $ and cut out every element $ a_l $ , $ a_{l + 1} $ , ..., $ a_r $ in this range; - stick some of the elements together in the same order they were in the array; - end up with multiple pieces, where every piece contains some of the elements and every element belongs to some piece. More formally, he partitions the sequence $ a_l $ , $ a_{l + 1} $ , ..., $ a_r $ into subsequences. He thinks a partitioning is beautiful if for every piece (subsequence) it holds that, if it has length $ x $ , then no value occurs strictly more than $ \lceil \frac{x}{2} \rceil $ times in it. He didn't pick a range yet, so he's wondering: for $ q $ ranges $ (l, r) $ , what is the minimum number of pieces he needs to partition the elements $ a_l $ , $ a_{l + 1} $ , ..., $ a_r $ into so that the partitioning is beautiful. A sequence $ b $ is a subsequence of an array $ a $ if $ b $ can be obtained from $ a $ by deleting some (possibly zero) elements. Note that it does not have to be contiguous.

N/A

N/A

In the first query, you can just put the whole array in one subsequence, since its length is $ 6 $ , and no value occurs more than $ 3 $ times in it. In the second query, the elements of the query range are $ [3,2,3,3] $ . You can't put them all in one subsequence, since its length is $ 4 $ , and $ 3 $ occurs more than $ 2 $ times. However, you can partition it into two subsequences: $ [3] $ and $ [2,3,3] $ .