#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int lis(vector<int>& a) {
    int n = a.size();
    vector<int> dp(n, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] <= a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, dp[i]);
    }
    return ans;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    cout << lis(a) << endl;
    return 0;
}

约定：$1 < n < 1000$，序列中的元素均为绝对值不超过$10^9$的整数。

第 1 题

若程序的输入为：

5
1 2 3 4 5

则程序的输出为（ ）
{{ select(1) }}

• 1
• 3
• 5
• 0

第 2 题

lis 函数的时间复杂度是（ ）
{{ select(2) }}

• $O(n)$
• $O(n \log n)$
• $O(n^2)$
• $O(n^3)$

第 3 题

在 lis 函数中，内层循环 j 的取值范围为 $0 \le j < i$。关于访问 dp[j] 是否可能越界，以下说法正确的是（ ）
{{ select(3) }}

• 不会越界，因为 dp 数组长度为 n，而 j 的最大值为 i-1，且 i 最大为 n-1，所以 j 最大为 n-2，始终合法
• 不会越界，因为 j 最小为 0，最大为 n-1，都在数组下标范围内
• 会越界，当 i = n-1 时，j 可能等于 n-1，超出数组范围
• 会越界，因为 j 没有限制在 [0, n-1] 内

第 4 题

若输入为：

5
5 4 3 2 1

则程序输出为（ ）
{{ select(4) }}

• 1
• 2
• 3
• 5

第 5 题

若将第 13 行的条件 if (a[j] <= a[i]) 修改为 if (a[j] < a[i])，即要求子序列严格递增。当输入为：

3
2 2 2

则程序的输出为（ ）
{{ select(5) }}

• 0
• 1
• 2
• 3

第 6 题

若将第 9 行的初始值 vector<int> dp(n, 1); 改为 vector<int> dp(n, 0);，其他代码不变。当输入为：

3
1 2 3

则程序的输出为（ ）
{{ select(6) }}

• 0
• 1
• 2
• 3