{"raw_statement":[{"iden":"statement","content":"The MaratonIME members like to have fun. As they enjoy having fun so much, they have invented a game named \"Cîrokime\". The game works as follows:\n\nFirst, n cups with _Cîroc_1 are lined up. In front of the i-th cup a number ai is written. It is guaranteed that ai < ai + 1, for all 1 ≤ i < n. Then, the numbers are covered and the game starts.\n\nThe player must then find the cup that has a certain number x. It is guaranteed that this cup exists. For this, he has to choose a cup i and drink the beverage. Then, the cup's number ai is revealed and if this number is equal to x the game finished. Otherwise, the player has to choose another cup and so on.\n\n\"Cîrokime\" is a traditional game among MaratonIME members, they play it every party. At the last party, Sussu had to drink all of the n cups because he found the right cup only at the end. He got sick for drinking so much and had to be carried home3\n\nHowever, the DESMAME4 is scheduled for May 13 and Sussu wants to restore his dignity. For this, he wants to know, in the worst case, what is the maximum number of cups that he will have to drink if he plays in the optimal way.\n\nThe first line has a single integer n, the number of cups. The second line has n integers ai, the values hidden in each cup.\n\nThe output has a single line with a single integer: the minimum number of cups that Sussu should drink, in the worst case, if he plays in the optimal way.\n\n1: Cîroc is a vodka brand made in France, known by its high sales price in market2\n\n2: Balalaika also works\n\n3: Based on real facts\n\n4: Pre-BIFE5 party\n\n5: University games that IME6 attends\n\n6: Institute of Mathematics and Statistics\n\n"},{"iden":"input","content":"The first line has a single integer n, the number of cups. The second line has n integers ai, the values hidden in each cup.  1 ≤ n ≤ 105  For all i, 1 ≤ ai ≤ 109  For i < n, ai < ai + 1 "},{"iden":"output","content":"The output has a single line with a single integer: the minimum number of cups that Sussu should drink, in the worst case, if he plays in the optimal way."},{"iden":"examples","content":"Input32 5 7Output2Input81 2 3 4 5 6 7 8Output4"},{"iden":"note","content":"1: Cîroc is a vodka brand made in France, known by its high sales price in market22: Balalaika also works3: Based on real facts4: Pre-BIFE5 party5: University games that IME6 attends6: Institute of Mathematics and Statistics"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ R, C \\in \\mathbb{Z}^+ $ with $ 1 \\leq R, C \\leq 25 $.  \nLet $ DP \\in \\mathbb{Z}^{(R+1) \\times (C+1)} $ be a 2D array such that:  \n- $ DP[0][j] = 0 $ for all $ j \\in \\{0, \\dots, C\\} $,  \n- $ DP[i][0] = 0 $ for all $ i \\in \\{0, \\dots, R\\} $,  \n- For $ i \\in \\{1, \\dots, R\\} $, $ j \\in \\{1, \\dots, C\\} $:  \n  $$\n  DP[i][j] = \n  \\begin{cases}\n  DP[i-1][j-1] + 1 & \\text{if } A[i] = B[j], \\\\\n  \\max(DP[i-1][j], DP[i][j-1]) & \\text{otherwise}.\n  \\end{cases}\n  $$\n\n**Constraints**  \n1. $ DP $ is generated by the standard LCS algorithm on two strings $ A $ and $ B $ over the alphabet $ \\{a, b, \\dots, z\\} $.  \n2. $ |A| = R $, $ |B| = C $.  \n\n**Objective**  \nReconstruct any pair of strings $ A = a_1 a_2 \\dots a_R $ and $ B = b_1 b_2 \\dots b_C $, where $ a_i, b_j \\in \\{a, \\dots, z\\} $, such that the LCS table produced by the algorithm matches the given $ DP $.","simple_statement":"Given a DP table from the LCS algorithm, find any two strings A and B (using lowercase letters) that could produce this table.","has_page_source":false}