Heck S. Quincy（朋友们称他为 Hex）负责四城地区（Quad Cities）以及孤星州双子城（Twin Cities）的回收工作。他负责的项目之一是在城市各处放置大型回收箱。由于运输这些回收箱的费用非常昂贵，他尽量让回收箱在某个地点放置尽可能长的时间，并每周清空一次。只要回收箱在每周结束时是满的，他都愿意将其保留在某个地点。

Hex 对每个地点每周预计产生的可回收材料量（以立方米为单位）有非常可靠的估算。根据这些信息，他想知道何时安装合适大小的回收箱以最大化回收材料的总量。他会将回收箱保留在该地点，直到（但不包括）预计回收箱无法装满的那一周。

例如，假设 Hex 对未来七周的估算如下：2 5 7 3 5 10 2。Hex 有几种放置回收箱的选择，包括：

• 从第 1 周到第 7 周放置一个容量为 2 的回收箱，回收量为 $14\,\text{m}^3$
• 从第 2 周到第 3 周放置一个容量为 5 的回收箱，回收量为 $10\,\text{m}^3$
• 从第 2 周到第 6 周放置一个容量为 3 的回收箱，回收量为 $15\,\text{m}^3$（这是可能的最大值）

Hex 不会从第 2 周到第 6 周放置一个容量为 5 的回收箱，因为在第 4 周它无法被装满。

输入格式

输入的第一行包含一个正整数 $n$ ($n \le 100\,000$)，表示 Hex 拥有估算的周数。周数编号为 1 到 $n$。接下来是 $n$ 个非负整数，按顺序给出了 $n$ 周中每一周预计的回收量。这些数值可能分布在多行中。

输出格式

输出三个整数 $s$、$e$ 和 $r$，其中 $s$ 和 $e$ 分别是放置回收箱的起始周和结束周，以最大化总回收量，而 $r$ 是该最大回收量。如果有两个或更多的时间段能达到相同的最大回收量，请输出 $s$ 值最小的那一个。

样例

样例输入 1

7
2 5 7 3 5
10 2

样例输出 1

2 6 15

样例输入 2

8
2 5 7 3 5
10 2 4

样例输出 2

1 8 16