由于现有的奶牛约会网站（如 eHarmoony、Moosk、Plenty of Cows）令奶牛们感到失望，Farmer John 决定推出一个新的奶牛约会网站。该网站基于一种精妙的专有匹配算法，根据奶牛和公牛广泛的共同兴趣进行匹配。

Bessie 为了寻找情人节谷仓舞会的舞伴，决定尝试这个网站。在注册账号后，FJ 的算法为她提供了一份包含 $N$ 个潜在匹配对象的列表（$1\leq N \leq 10^6$）。经过浏览，Bessie 得出结论：每头公牛接受她舞会邀请的概率为 $p_i$（$0

Bessie 决定向列表中一个连续区间内的每头公牛发送邀请。一如既往地，她希望恰好能有一位舞伴。请帮助 Bessie 找到如果她选择了正确的区间，能够获得恰好一个接受邀请的最大概率。

输入格式

第一行包含一个整数 $N$（$1 \leq N \leq 10^6$）。接下来的 $N$ 行，每行包含一个整数，表示 $10^6 \times p_i$ 的值。

在至少 25% 的测试用例中，保证 $N \leq 4000$。

输出格式

输出 $10^6$ 乘以获得恰好一个接受邀请的最大概率的结果，向下取整到最接近的整数。

样例

样例输入 1

3
300000
400000
350000

样例输出 1

470000

说明

选择第 2 头到第 3 头奶牛的区间可以获得最大概率。

需要注意的是，在解决此问题时，应谨慎处理浮点数精度。建议至少使用 double（64 位浮点数），而不要使用 float（32 位浮点数）。

Problem credits: Ethan Guo