CF1324E Sleeping Schedule

Vova had a pretty weird sleeping schedule. There are $ h $ hours in a day. Vova will sleep exactly $ n $ times. The $ i $ -th time he will sleep exactly after $ a_i $ hours from the time he woke up. You can assume that Vova woke up exactly at the beginning of this story (the initial time is $ 0 $ ). Each time Vova sleeps exactly one day (in other words, $ h $ hours). Vova thinks that the $ i $ -th sleeping time is good if he starts to sleep between hours $ l $ and $ r $ inclusive. Vova can control himself and before the $ i $ -th time can choose between two options: go to sleep after $ a_i $ hours or after $ a_i - 1 $ hours. Your task is to say the maximum number of good sleeping times Vova can obtain if he acts optimally.

N/A

N/A

The maximum number of good times in the example is $ 3 $ . The story starts from $ t=0 $ . Then Vova goes to sleep after $ a_1 - 1 $ hours, now the time is $ 15 $ . This time is not good. Then Vova goes to sleep after $ a_2 - 1 $ hours, now the time is $ 15 + 16 = 7 $ . This time is also not good. Then Vova goes to sleep after $ a_3 $ hours, now the time is $ 7 + 14 = 21 $ . This time is good. Then Vova goes to sleep after $ a_4 - 1 $ hours, now the time is $ 21 + 19 = 16 $ . This time is not good. Then Vova goes to sleep after $ a_5 $ hours, now the time is $ 16 + 20 = 12 $ . This time is not good. Then Vova goes to sleep after $ a_6 $ hours, now the time is $ 12 + 11 = 23 $ . This time is good. Then Vova goes to sleep after $ a_7 $ hours, now the time is $ 23 + 22 = 21 $ . This time is also good.