题干：

题目大意：

有n个人为成一个圈，其中第i个人想要r[i]种不同的礼物，相邻的两个人可以聊天，炫耀自己的礼物。如果两个相邻的人拥有同一种礼物，则双方都会很不高兴，问最少需要多少种不同的礼物才能满足所有人的需求，假设每种礼物有无限多个。 n<=100000

解题报告：

http://www.cnblogs.com/kickit/p/7619889.html

http://www.bubuko.com/infodetail-645767.html

总之就是偶数个的时候直接贪出相邻两者的最大值就可以。

              奇数的时候：先单独安排第一个，并以这一个为分界线分为左右两个区域部分，然后剩下的分奇偶进行安排（第奇数个尽量往右安排，第偶数个尽量往左安排），然后安排到最后一个一定是尽量往右安排的，然后我们看这个是否和第一个有冲突就行了，如果没有冲突那一定是可以的，如果有冲突那一定就是说明我们用的李无数是不够的，因为我们这样一定是最优解了。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX = 2e5 + 5;
int a[MAX];
int L[MAX],R[MAX];
int n;
bool ok(int x) {
	int l=a[1],r=x-a[1];
	L[1]=a[1];R[1]=0;
	for(int i = 2; i<=n; i++) {
		if(i%2==1) {
			R[i] = min(r-R[i-1],a[i]);
			L[i] = a[i]-R[i];
		}
		else {
			L[i] = min(l-L[i-1],a[i]);
			R[i] = a[i]-L[i];
		}
	}
	return L[n]==0;//填L[n]<=0也可以AC，，但是在这里还是==0比较好理解，因为L和R这两个数组都不存在为负情况。
	
}
int main()
{
	while(~scanf("%d",&n)) {
		if(n == 0) break;
		int maxx = 0;
		for(int i = 1; i<=n; i++) {
			scanf("%d",a+i);
			maxx = max(maxx,a[i]+a[i-1]);
		}
		maxx = max(maxx,a[1]+a[n]);
		if(n == 1) {
			printf("%d\n",a[1]);continue;
		}
		else if(n % 2 == 0) {
			printf("%d\n",maxx);continue;
		}
		int l = maxx,r = INF;
		int mid = (l+r)>>1;
		while(l < r) {
			mid = (l+r)>>1;
			if(ok(mid)) r = mid;
			else l = mid+1;
		}
		printf("%d\n",l);
	}
	return 0 ;
 }