该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有 $n$ 个元素的数组 $a_1,a_2,a_3,\cdots,a_n$，求该数组的最长上升子序列的长度与方案数。因为方案数很大，需要输出方案数取模 $10^9 + 7$ 的结果。 ​

输入格式

第一行输入一个整数 $n$，表示数组长度。 ​ 第二行输入 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示数组中的每一个数。 ​

输出格式

一行两个整数，表示最长上升子序列的长度与方案数，之间用空格隔开。 ​

样例输入输出

5 1 2 8 6 4

3 3

说明/提示

样例解释

最长上升子序列的长度为 $3$，并且有 $3$ 个，分别为 $[1,2,8],[1,2,6],[1,2,4]$ 。 ​

数据范围

对于 $30\%$ 的数据，$1\le n\le 20$ ​ 对于 $100\%$ 的数据，$1\le n\le 2000$，$a_i$ 在 int 范围之内。