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,
- Output the number of ways of generating this lenght modula 10000007.
- 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