Background

Special for beginners, ^_^

Description

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

Format

Input

每个测试点包含多组数据，对于每组数据：

第一行：单个整数n。

第二行：n 个不超过1e6的整数 $h_1，h_2，...h_n$。

单个测试点的n总数不超过2e6。

Output

对于每组数据，输出两行：

第一行：最大矩形的面积。

第二行：最大矩形的数量。

Samples

5
3 2 2 1 2
1
1

6
1
1
1

Limitation

1s, 1024KiB for each test case.

Source

YACS 578

2023年9月月赛丙组T5