AT_abc468_f [ABC468F] Chmax

You are given a positive integer $ N $ and a permutation $ P=(P_1,P_2,\ldots,P_N) $ of $ (1,2,\ldots,N) $ . There are variables $ x,y,c $ . Initially, $ x=y=c=0 $ . For $ k=1,2,\ldots,N $ in this order, you perform one of the following operations: - Operation $ 1 $ : Increase $ c $ by $ 1 $ if $ x < P_k $ . Then, replace $ x $ with $ \max(x,P_k) $ . - Operation $ 2 $ : Increase $ c $ by $ 1 $ if $ y < P_k $ . Then, replace $ y $ with $ \max(y,P_k) $ . Find the maximum possible final value of $ c $ .

The input is given from Standard Input in the following format: > $ N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $

Output the answer.

### Sample Explanation 1 By performing the operations as follows, you can achieve $ c=4 $ : - For $ k=1 $ : Perform operation $ 1 $ . Then, $ (x,y,c)=(4,0,1) $ . - For $ k=2 $ : Perform operation $ 1 $ . Then, $ (x,y,c)=(4,0,1) $ . - For $ k=3 $ : Perform operation $ 2 $ . Then, $ (x,y,c)=(4,1,2) $ . - For $ k=4 $ : Perform operation $ 2 $ . Then, $ (x,y,c)=(4,2,3) $ . - For $ k=5 $ : Perform operation $ 2 $ . Then, $ (x,y,c)=(4,5,4) $ . $ c $ cannot be made greater than $ 4 $ no matter how you perform the operations, so output $ 4 $ . ### Constraints - $ 1\le N\le 5\times 10^5 $ - $ P $ is a permutation of $ (1,2,\ldots,N) $ . - All input values are integers.