Sage is a bright shining star when it comes down to sorting stuff; she can handle multiple sorting scenarios in a fashion that can only be described as “awesome, spectacular, and, above all else, awe- sometacular”. By performing sorts of all sorts during the years, Sage has developed interesting skills that she plans on using for sorting information efficiently in the technology world, where the “big bucks” are. Currently, Sage is working on a mysterious heuristic that attempts to sort data in two passes. The first one is the smoothing phase and the second one is the sorting phase. The general idea is that the smoothing phase leaves the data almost ordered so that the sorting phase can be done very efficiently. Sage is in the process of testing and validating the effectiveness of the sorting phase. She has developed a quantitative measure on an array of values called the smooth factor. For an array a = a1,a2,...,an of values, the smooth factor of a is the length of a longest subarray ap,...,aq of a (1≤p≤q≤n)suchthatthereisatmostonei(p<i≤q)suchthatai−1 >ai,where<issomefixed order on the values in a. The higher the smooth factor, the more effective the smooth phase is. For example, under the natural order of integer numbers, for the array 1, 2, 3 the smooth factor is 3 and for the array 1, 2, 1, 2, 1, 2, 3, 1 the smooth factor is 5. In the first case the entire array serves as a witness and in the second case the witness is 1, 2, 1, 2, 3. Sage has gathered some output sample arrays of the smoothing process and would like to know how effective this process is before she signs any deals with the information moguls. In other words, for a given input array, she wants to compute its smooth factor. Can you help her? Input The input consists of several test cases. Each test case consists of two lines. The first line of a test case contains an integer n (1 ≤ n ≤ 105) indicating the length of the sample array. The second line contains n blank-separated integer numbers a1, . . . , an (with 0 ≤ |ai| < 108). Output For each test case, output a line with the smooth factor of the array a1, . . . , an. Sample Input 3 123 1 0 8 12121231 4 1 -10 -100 -100 Sample Output 3 1
2/2 5 3