#P18784. [TOI22] 犀鸟的合唱

[TOI22] 犀鸟的合唱

犀鸟的合唱

两只犀鸟要合唱一首包含 NN 个音符的歌曲。音符按顺序编号为 0,1,…,N−10,1,\ldots,N-1,第 ii 个音符的音高为 AiA_i。

每个音符必须恰好交给其中一只鸟演唱。两只鸟各自演唱的音符都保持歌曲中的原有顺序。

如果一只鸟依次演唱的音高为 x1,x2,…,xkx_1,x_2,\ldots,x_k,它的疲劳值为

∑j=2k∣xj−xj−1∣.\sum_{j=2}^{k}|x_j-x_{j-1}|.

演唱零个或一个音符的鸟,疲劳值为 00。

请给出一种分配方案,使两只鸟的疲劳值之和最小。存在多个最优方案时,输出任意一个即可。

输入格式

第一行一个整数 NN。

第二行 NN 个整数 A0,A1,…,AN−1A_0,A_1,\ldots,A_{N-1}。

输出格式

输出 NN 个整数 V0,V1,…,VN−1V_0,V_1,\ldots,V_{N-1},其中每个整数为 00 或 11,表示对应音符交给哪只鸟演唱。

不需要输出最小疲劳值。

数据范围

  • 1≤N≤2000001\le N\le 200000。
  • 1≤Ai≤1091\le A_i\le10^9。

时间限制:1 秒。内存限制:512 MB。

子任务

子任务 分值 附加限制
1 7 N≤20N\le20
2 11 A0≤A1≤⋯≤AN−1A_0\le A_1\le\cdots\le A_{N-1}
3 16 N≤100N\le100
4 18 数组中不同音高的数量不超过 2020
5 25 N≤1000N\le1000
6 23 无附加限制

样例

5
1 5 6 3 2
1 0 0 1 1

样例说明

第一只鸟演唱音高 5,65,6,疲劳值为 11;第二只鸟演唱音高 1,3,21,3,2,疲劳值为 2+1=32+1=3。总疲劳值为 44,为最优值。

将两只鸟的编号互换,得到 0 1 1 0 0,也是合法的最优方案。