Codeforces Round #327 (Div. 2)-C. Median Smoothing

原题链接

C. Median Smoothing

time limit per test

memory limit per test

input

output

median smoothing

a1, a2, ..., anwill result a new sequenceb1, b2, ..., bnobtained by the following algorithm:

• b1 = a1,bn = an, that is, the first and the last number of the new sequence match the corresponding numbers of the original sequence.
• i = 2, ..., n - 1valuebiis equal to themedianof three valuesai - 1,aiandai + 1.

median

In order to make the task easier, Vasya decided to apply the method to sequences consisting of zeros and ones only.

stable, if it does not change when the median smoothing is applied to it.

Now Vasya wonders, whether the sequence always eventually becomes stable. He asks you to write a program that, given a sequence of zeros and ones, will determine whether it ever becomes stable. Moreover, if it ever becomes stable, then you should determine what will it look like and how many times one needs to apply the median smoothing algorithm to initial sequence in order to obtain a stable one.

Input

n(3 ≤ n ≤ 500 000)— the length of the initial sequence.

nintegersa1, a2, ..., an(aiorai), giving the initial sequence itself.

Output

 - 1.

n

Examples

input

40 0 1 1

output

00 0 1 1

input

50 1 0 1 0

output

20 0 0 0 0

若num[i] == num[i-1] || num[i] == num[i+1]则num[i]它处于稳定状态，不需要改变。num需要改变[i] != num[i-1] && num[i] != num[i+1]找到一串需要变化的数字。如果长度为d，则变化次数为d = d & 1 ? d / 2 + 1 : d / 2;

#include <bits/stdc++.h>#define maxn 500005#define MOD 1000000007using namespace std;typedef long long ll;int num[maxn];int main(){//freopen("in.txt", "r", stdin);int n, maxs = 0;scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", num+i);for(int i = 2; i < n; i++){if(num[i] == num[i+1] || num[i] == num[i-1]) continue;int h1 = i, h2;for(i++; i < n; i++){if(num[i] == num[i-1] || num[i] == num[i+1]){h2 = i - 1;break;}} if(i == n) h2 = n - 1;int d = h2 - h1 + 1;d = d & 1 ? d / 2 + 1 : d / 2;maxs = max(maxs, d);for(int j = 1; j <= d; j++){if(j&1){num[h1] = 1 - num[h1];if(h1 != h2)num[h2] = 1 - num[h2];}h1++;h2--;}}printf("%d\n", maxs);printf("%d", num[1]);for(int i = 2; i <= n; i++) printf(" %d", num[i]);puts("");return 0;}