Description：

一个正整数序列，一些位置已经填上了值，求一个满足以下条件的序列且使 $a_n$ 最大。

1、 $a_1=1$

2、 $\forall i\in[1,n),a_i\le a_{i+1}\le a_i+1$

3、所有在 $a$ 中出现过的数出现次数 $\in[2,5]$

$1\le n \le 200000$

Solution：

记一个 $u$ 一个 $d$ 表示当前的上下界，由于有出现次数限制还要记一个当前出现次数，从前往后扫，对于上界，满两个就加一，对于下界，满五个才加一，如果有数，就更新对应上下界，注意由于想让 $d$ 尽量小，所以要填一个新数时应让他的出现次数尽量小，以便以后尽量赋值，由于想让 $u$ 尽量大，所以要填一个新数时应增加他前面的数的出现次数而让下一位能直接再增大，注意判断无解的情况，最后一个数不能只填一位，由于要最大化 $a_n$ 的值，所以最后在按 $u$ 从后往前推一遍，注意再推的时候还要保证合法性。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 200010

int num[MAXN];

struct limit

{

	int k,t;

	limit(int k_ = 0,int t_ = 0){k = k_;t = t_;}

}u[MAXN],d[MAXN];

int t[MAXN];

int main()

{

	freopen("seq.in","r",stdin);

	freopen("seq.out","w",stdout);

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&num[i]);

	if(num[1] != 1 && num[1] != 0){puts("-1");return 0;}

	u[1] = limit(1,1);d[1] = limit(1,1);

	for(int i = 2;i <= n;++i)

	{

		d[i] = d[i - 1];++d[i].t;

		if(d[i].t > 5){++d[i].k;d[i].t = 1;}

		u[i] = u[i - 1];++u[i].t;

		if(u[i].t > 2){++u[i].k;u[i].t = 1;}

		if(num[i] != 0)

		{

			if(u[i].k < num[i] || d[i].k > num[i]){puts("-1");return 0;}

			if(num[i] > d[i].k)d[i].t = 1;

			if(num[i] < u[i].k)u[i].t = 2;

			d[i].k = u[i].k = num[i]; 

		}

	}

	if(u[n].t == 1)--u[n].k;

	if(u[n].k < d[n].k){puts("-1");return 0;}

	++t[num[n] = u[n].k];

	cout << u[n].k << endl;

	for(int i = n - 1;i >= 1;--i)

	{

		num[i] = min(u[i].k,num[i + 1]);

		if(t[num[i]] + 1 > 5)--num[i];

		++t[num[i]];

	}

	for(int i = 1;i <= n;++i)

	{

		cout << num[i] << " ";

	}

	cout << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}