题目描述

$Bob$ 正在玩“橙子” 游戏，最开始给定 $n$ 堆橙子，第 $i$ 橙子有 $a_i$ 个。

游戏开始, $Bob$ 可以输入一个区间 $[l,r]$ 和 $x(x\le a_i)$, 对于区间内第 $i$ 堆橙子，$Bob$ 可以吃掉 $x$ 个橙子。即： $Bob$ 输入的数据要保证 $l\le i \le r$ , $x \le a_i$ , $Bob$ 能够吃掉 $(r-l+1) \times x$ 个橙子。

$Bob$ 当然想吃掉最多的的“橙子” ，请帮忙输入 $l,r,x$ ，确保 $Bob$ 吃掉最多的 “橙子”，并输出能吃掉的最多的橙子。

如果有多种方案都能吃到最多的橙子，请输出区间长度最短且左端点最小的方案。

输入格式

输入格式如下

$n$

$a_1 \dots a_n$

输出格式

两行，第一行三个整数 $l,r,x$

第二行一个整数，表示 $Bob$ 能吃掉的最多的橙子。

6
2 4 4 9 4 9

2 6 4
20

样例1解释

选择区间 $[2,6]$ ，对应的橙子数量是 $[4,4,9,4,9]$ , 每堆橙子吃掉 $4$ 个，总共可以吃掉 $20$ 个橙子。

6
200 4 4 9 4 9

1 1 200
200

数据规模与约定

$subtask1$ : $1 \le n \le 100,1 \le a_i \le 100$ , $20$ 分

$subtask2$ : $1 \le n \le 10^3,1 \le a_i \le 10^3$ , $30$ 分

$subtask3$ : $1 \le n \le 10^4,1 \le a_i \le 10^4$ , $40$ 分

$subtask4$ : $1 \le n \le 10^4,1 \le a_i \le 10^9$ , $10$ 分

注意：题目中空间只有 $256$ M