Longest Non‐decreasing Subsequence Variants

You are given a sequence of positive integers \(x_1, x_2, \ldots, x_n\). Solve the following three problems:

1. Compute \(s\), the length of the longest non‐decreasing subsequence (LNDS) of the sequence. Here a subsequence is defined by indices \(a_1, a_2, \ldots, a_s\) with \(1 \le a_1 < a_2 < \cdots < a_s \le n\) and \(x_{a_1} \le x_{a_2} \le \cdots \le x_{a_s}\).
2. If each element of the sequence may be used at most once, compute the maximum number of non‐decreasing subsequences of length \(s\) (each extracted using distinct indices) that can be obtained from the given sequence.
3. Now, suppose that in the subsequences you extract, the first element \(x_1\) and the last element \(x_n\) are "reusable" – that is, they may be used in every subsequence, while every other element may still be used at most once. Under this modification, compute the maximum number of different non‐decreasing subsequences of length \(s\) that can be obtained. Two subsequences \(S\) and \(T\) (with chosen indices \(a_1, a_2, \ldots, a_s\) and \(b_1, b_2, \ldots, b_s\) respectively) are considered different if \(\exists i\in[1,s]\) such that \(a_i \neq b_i\).

The output should be three integers: \(s\), the answer for (2), and the answer for (3), separated by spaces.

Hint: You may first compute for each index \(i\) the length \(f[i]\) of the longest non‐decreasing subsequence ending at \(i\) and \(g[i]\) of the longest non‐decreasing subsequence starting at \(i\). An index \(i\) can appear in some LNDS if \(f[i] + g[i] - 1 = s\). Then, by constructing a directed acyclic graph on those indices with an edge from \(i\) to \(j\) (\(i < j\)) if \(x_i \le x_j\), \(f[i] + 1 = f[j]\), and \(f[i] + g[j] = s\), the problems (2) and (3) reduce to finding a maximum collection of vertex‐disjoint paths from a source (connected to all indices with \(f[i]=1\)) to a sink (connected from all indices with \(g[i]=1\)). In the network for (3) the vertices corresponding to \(x_1\) and \(x_n\) are given infinite capacity.

inputFormat

The first line contains an integer \(n\) (the length of the sequence).
The second line contains \(n\) positive integers \(x_1, x_2, \ldots, x_n\) separated by spaces.

outputFormat

Output three space-separated integers: \(s\) (the length of the longest non-decreasing subsequence), the maximum number of disjoint LNDS of length \(s\) (each element used at most once), and the maximum number of different LNDS of length \(s\) when \(x_1\) and \(x_n\) may be reused.

sample

4
1 2 1 2

3 1 2