CF1404C Fixed Point Removal

Let $ a_1, \ldots, a_n $ be an array of $ n $ positive integers. In one operation, you can choose an index $ i $ such that $ a_i = i $ , and remove $ a_i $ from the array (after the removal, the remaining parts are concatenated). The weight of $ a $ is defined as the maximum number of elements you can remove. You must answer $ q $ independent queries $ (x, y) $ : after replacing the $ x $ first elements of $ a $ and the $ y $ last elements of $ a $ by $ n+1 $ (making them impossible to remove), what would be the weight of $ a $ ?

N/A

N/A

Explanation of the first query: After making first $ x = 3 $ and last $ y = 1 $ elements impossible to remove, $ a $ becomes $ [\times, \times, \times, 9, 5, 4, 6, 5, 7, 8, 3, 11, \times] $ (we represent $ 14 $ as $ \times $ for clarity). Here is a strategy that removes $ 5 $ elements (the element removed is colored in red): - $ [\times, \times, \times, 9, \color{red}{5}, 4, 6, 5, 7, 8, 3, 11, \times] $ - $ [\times, \times, \times, 9, 4, 6, 5, 7, 8, 3, \color{red}{11}, \times] $ - $ [\times, \times, \times, 9, 4, \color{red}{6}, 5, 7, 8, 3, \times] $ - $ [\times, \times, \times, 9, 4, 5, 7, \color{red}{8}, 3, \times] $ - $ [\times, \times, \times, 9, 4, 5, \color{red}{7}, 3, \times] $ - $ [\times, \times, \times, 9, 4, 5, 3, \times] $ (final state) It is impossible to remove more than $ 5 $ elements, hence the weight is $ 5 $ .