CF1905F Field Should Not Be Empty

You are given a permutation $ ^{\dagger} $ $ p $ of length $ n $ . We call index $ x $ good if for all $ y < x $ it holds that $ p_y < p_x $ and for all $ y > x $ it holds that $ p_y > p_x $ . We call $ f(p) $ the number of good indices in $ p $ . You can perform the following operation: pick $ 2 $ distinct indices $ i $ and $ j $ and swap elements $ p_i $ and $ p_j $ . Find the maximum value of $ f(p) $ after applying the aforementioned operation exactly once. $ ^{\dagger} $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array).

N/A

N/A

In the first test case, $ p = [1,2,3,4,5] $ and $ f(p)=5 $ which is already maximum possible. But must perform the operation anyway. We can get $ f(p)=3 $ by choosing $ i=1 $ and $ j=2 $ which makes $ p = [2,1,3,4,5] $ . In the second test case, we can transform $ p $ into $ [1,2,3,4,5] $ by choosing $ i=1 $ and $ j=2 $ . Thus $ f(p)=5 $ .