Anti Monotonicity Revisited

Given a permutation of (1, 2, 3, . . . , n), find the length of the longest Anti-Monotonous subsequence of this permutation, i.e. a subsequence A[0] . . . A[k] that satisfies: A[0] > A[1] < A[2] > A[3] < ...A[k] Also,

1. Output the number of ways of generating this lenght modula 10000007.
2. Output the mean value of the lenghts of the longest Anti-Monotonous subsequence over all per- mutations of (1, 2, 3, . . . , n). Round to integer. Input For each test case, the first line contains the number n (0 ≤ n ≤ 100000) followed by n integers representing the permutation. Output For each test case, output a triple of integer followed by a new line — the length of the longest subsequence, the number of the ways module 10000007, and the mean value of the lengths over all permutations rounded to integer. Sample Input 10 1 9 2 3 4 10 5 7 8 6 5 24135 Sample Output 697 354