Longest Increasing Subsequence

Problem Source

Network Flow 24 Problems

Problem Description

Given a sequence of positive integers $x_1 \sim x_n$ (an increasing subsequence below means non-strictly increasing):

1. Compute the length $s$ of its longest increasing subsequence.
2. Compute the maximum number of increasing subsequences of length $s$ that can be taken from the given sequence (no element may be reused).
3. If $x_1$ and $x_n$ are allowed to be used multiple times in the taken subsequences, compute the maximum number of increasing subsequences of length $s$ that can be taken.

Input Format

The first line contains one positive integer $n (1\leq n\leq 500)$, the length of the given sequence. The next line contains $n$ positive integers $x_1, x_2, \dots, x_n$.

Output Format

Three lines, each with one integer, giving the answer to the corresponding question above.

Sample Input

4
3 6 2 5

Sample Output

2
2
3

Constraints

$1\leq n\leq 500$.

Hint

• First compute the longest increasing subsequence length $s$ with DP. Questions 2 and 3 are classic maximum-flow problems: build a layered network where each element is split into an in-node and an out-node (capacity 1, or infinite for $x_1$ and $x_n$ in question 3), and connect elements that can extend an increasing subsequence.