e_custom_ll.cpp

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

int n;
int *aita;

void print_solution(int tertiary){

	int start = 0;
	int maxes[2] = {0, 0};

	auto print_painters_for = [&](int end){
		string pattern;
		if (maxes[0] > maxes[1]){
			pattern = "1 2 ";
		} else {
			pattern = "2 1 ";
		}

		auto length = end - start;
		for (int i = 0; i < length/2; i++){
			cout << pattern;
		}
		if (length & 1) {
			cout << pattern.substr(0, 2);
		}
	};

	for (int i = 0; i < n-1; i++) {
		int h = aita[i];

		if (h <= tertiary && aita[i+1] > tertiary) {
			print_painters_for(i);
			cout << "3 ";
			start = i+1;
			maxes[0] = 0;
			maxes[1] = 0;
		} else {
			auto p = &maxes[(i-start)&1];
			*p = max(*p, h);
		}
	}
	print_painters_for(n);
	cout << endl;
}

struct Lauta{
	Lauta *prev, *next;

	int no;

	bool active, even;
	int maxodd, maxeven;
};

int *tree;

bool lessThan(Lauta *a, Lauta *b) {
	return a->maxodd > b->maxodd;
}

int parent(int x) {
	return (x - 1) / 2;
}

void calc(int i){
	tree[i] = max(tree[i*2+1], tree[i*2+2]);
	if (i != 0) {
		calc(parent(i));
	}
}

int nearest_power;
void update(int i, int x) {
	i += nearest_power-1;
	tree[i] = x;
	calc(parent(i));
}

list<Lauta> laudat;

void merge(Lauta *a, Lauta *b) {
	if (a->even) {
		a->maxodd = max(a->maxodd, b->maxodd);
		a->maxeven = max(a->maxeven, b->maxeven);
	} else {
		a->maxodd = max(a->maxodd, b->maxeven);
		a->maxeven = max(a->maxeven, b->maxodd);
	}

	a->even = a->even == b->even;
	
	update(b->no, 0);
	
	a->next = b->next;
	b->next->prev = a;
}

int main(){
	cin >> n;

	aita = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> aita[i];
	}

	if (n == 1){
		cout << aita[0] << ' ' << 1 << endl;
		cout << 1 << endl;
		return 0;
	}

	// ratkaiseminen

	auto list_elements = new Lauta[n];
	auto wakeup = new Lauta*[n];

	for (int i = 0; i < n; i++){
		Lauta lauta = {
			.prev = &list_elements[i-1],
			.next = &list_elements[i+1],
			.no = i,
			.active = false,
			.even = false,
			.maxodd = aita[i],
			.maxeven = 0
		};
		list_elements[i] = lauta;
		wakeup[i] = &list_elements[i];
	}

	Lauta sentinel;
	sentinel.active = false;
	wakeup[0]->prev = &sentinel;
	wakeup[n-1]->next = &sentinel;

	sort(wakeup, wakeup+n, lessThan);


	nearest_power = 1;
	while(nearest_power < n) nearest_power <<= 1;

	int tree_size = nearest_power * 2 - 1;
	tree = new int[tree_size];
	for(int i = 0; i < tree_size; i++) tree[i] = 0;

	int primary = *max_element(aita, aita+n);
	int secondary = primary;
	int tertiary = primary;

	for (int i = 0; i < n; i++) {
		auto it = wakeup[i];
		
		it->active = true;

		auto next = it->next;
		auto prev = it->prev;
		if (next->active) {
			merge(it, next);
		}
		if (prev->active) {
			merge(prev, it);
			it = prev;
		}

		update(it->no, min(it->maxodd, it->maxeven));

		int new_tertiary = (i != n-1 ? wakeup[i+1]->maxodd : 0);
		int new_secondary = max(tertiary, tree[0]);
		if (new_secondary+new_tertiary < secondary+tertiary) {
			secondary = new_secondary;
			tertiary = new_tertiary;
		}
	}

	// output
	cout << primary+secondary+tertiary << ' ';
	cout << (tertiary == 0 ? 2 : 3) << endl;

	print_solution(tertiary);
}