|
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 length modula 10000007. 2) Output the mean value of the lengths of the longest Anti-Monotonous subsequence over all permutations of (1,2,3, ... , n). Round to integer.
For each test case, the first line contains the number n (0 <= n <= 100000) followed by n integers representing the permutation.
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 | Sample Output |
10 1 9 2 3 4 10 5 7 8 6 5 2 4 1 3 5 |
6 9 7 3 5 4 |
Problemsetter: Rodrigo Burgos Domínguez, Josh Bao