题目描述

直方图由 $n$ 列小方格合并而成。每列有若干方格，其中第 $i$ 列方格的数量为 $h_i$。请在方格图的轮廓中找到一个最大面积的矩形，输出这个矩形的面积与最大矩形的数量。

例如在上图中 $n=5$，$h = (3,2,2,1,2)$，最大面积为 $3\times2=6$，只有 $1$ 个。

输入格式

• 第一行：单个整数 $n$
• 第二行：$n$ 个整数 $h_1, h_2, \dots, h_n$

输出格式

• 第一行：最大矩形的面积
• 第二行：最大矩形的数量

数据范围

• $30\%$ 的数据，$1\leq n\leq 100$
• $60\%$ 的数据，$1\leq n\leq 20,000$
• $100\%$ 的数据，$1\leq n\leq 300,000$
• $0\leq h_i\leq 500,000$

样例数据

输入:

5
3 2 2 1 2

输出:

6
1