#CW19. 消除环(cycle)

消除环(cycle)

题目描述

给定一个长度为 nn 的整数序列 a1,a2,…,ana_1,a_2,\ldots,a_n,这些元素首尾相连,形成一个环。也就是,aia_i 与 ai+1a_{i+1} 相邻(1≤i<n1 \le i<n),ana_n 和 a1a_1 相邻。

你要按照一定的规则消除这个环中的所有元素。

初始时,你有一个能力值 xx。对于每次要消除的元素 aia_i,必须满足:ai≤xa_i \le x。

你可以任意选择一个元素作为第一个元素来首先消除。除了第一个元素可以任意选择以外,之后,每次只能选择当前仍存在的、至多有一个相邻元素尚未被消除的元素。

消除一个元素 aia_i 后,能力值立即增加其数值:x←x+aix \leftarrow x+a_i。

求消除整个环所需的最小初始能力值 xx。

输入格式

第一行一个整数 nn,表示序列长度。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

输出格式

输出一个整数,表示最小的初始能力值 xx。

样例 1 输入

5
5 0 10 6 1

样例 1 输出

4

样例 2 输入

7
20 23 7 2 3 7 1

样例 2 输出

2

数据范围

对于所有测试数据,保证:3≤n≤5×1053 \le n \le 5 \times 10^5,0≤ai≤10130 \le a_i \le 10^{13}。

分值 n≤n \le 特殊性质
2020 1010 无
10001000
1515 1000010000 ai≤100a_i \le 100
5×1055 \times 10^5 a1≤a2≤⋯≤ana_1 \le a_2 \le \cdots \le a_n
3030 无

本题按 subtask 计分:只有通过一个 subtask 的全部测试点,才能获得该 subtask 的分数。