CF1807B Grab the Candies

Mihai and Bianca are playing with bags of candies. They have a row $ a $ of $ n $ bags of candies. The $ i $ -th bag has $ a_i $ candies. The bags are given to the players in the order from the first bag to the $ n $ -th bag. If a bag has an even number of candies, Mihai grabs the bag. Otherwise, Bianca grabs the bag. Once a bag is grabbed, the number of candies in it gets added to the total number of candies of the player that took it. Mihai wants to show off, so he wants to reorder the array so that at any moment (except at the start when they both have no candies), Mihai will have strictly more candies than Bianca. Help Mihai find out if such a reordering exists.

N/A

N/A

In the first test case, Mihai can reorder the array as follows: $ [4, 1, 2, 3] $ . Then the process proceeds as follows: - the first bag has $ 4 $ candies, which is even, so Mihai takes it — Mihai has $ 4 $ candies, and Bianca has $ 0 $ . - the second bag has $ 1 $ candies, which is odd, so Bianca takes it — Mihai has $ 4 $ candies, and Bianca has $ 1 $ . - the third bag has $ 2 $ candies, which is even, so Mihai takes it — Mihai has $ 6 $ candies, and Bianca has $ 1 $ . - the fourth bag has $ 3 $ candies, which is odd, so Bianca takes it — Mihai has $ 6 $ candies, and Bianca has $ 4 $ . Since Mihai always has more candies than Bianca, this reordering works.