#include <bits/stdc++.h>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int next_power_2(int n) {
	return (1 << (32 - __builtin_clz(n - 1)));
}

struct Node {
	int val, pos;
	Node() {
		val = pos = 0;
	}
	Node(int v, int p) {
		val = v;
		pos = p;
	}
};

const Node NULL_NODE;

Node combine(Node left_node, Node right_node) {
	Node res;
	if (left_node.val >= right_node.val) {
		res.val = left_node.val;
		res.pos = left_node.pos;
	} else {
		res.val = right_node.val;
		res.pos = right_node.pos;
	}
	return res;
}

struct SegmentTree {	
	vector<Node> tree;
	int TREE_SIZE;
	
	SegmentTree(int n) {
		TREE_SIZE = next_power_2(n);
		tree = vector<Node> (TREE_SIZE << 1, NULL_NODE);
		for (int i = 1; i < TREE_SIZE; i++)
			tree[i].pos = tree[i + TREE_SIZE].pos = i;
	}
	
	void update(int pos, int x) {
		int i = pos;
		i += TREE_SIZE;
		Node node(x, pos);
		tree[i] = combine(tree[i], node);
		while (i > 1) {
			i >>= 1;
			tree[i] = combine(tree[i << 1], tree[i << 1 | 1]);
		}
	}
	
	Node query(int left, int right) {
		Node res = NULL_NODE;
		left += TREE_SIZE;
		right += TREE_SIZE;
		while (left <= right) {
			if (left & 1)
				res = combine(res, tree[left++]);
			if (!(right & 1))
				res = combine(res, tree[right--]);
			left >>= 1;
			right >>= 1;
		}
		return res ;
	}
};

int main() {
	int n;
	fin >> n;
	
	vector<int> a(n), tmp(n), prev(n);
	for (int i = 0; i < n; i++) {
		fin >> a[i];
		tmp[i] = a[i];
	}
	
	// f[i] = lungimea maxima a unui subsir strict crescator care 
	// are ultimul element a[i] (se termina pe pozitia i)
	// f[i] = 1 + max{f[j] | j < i, a[j] < a[i]}
	// prev[i] = j, pozitia pentru care se realizeaza maximul anterior
	// prev[i] = 0, daca nu exista o alta valoare precedenta
	
	sort(tmp.begin(), tmp.end());
	tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
	
	auto idx = [&](int val) {
		return lower_bound(tmp.begin(), tmp.end(), val) - tmp.begin();
	};
	
	for (int i = 0; i < n; i++)
		a[i] = 1 + idx(a[i]);
		
	auto print = [&]() -> void {
		for (int i = 0; i < (int)tmp.size(); i++)
			cout << tmp[i] << " ";
		cout << "\n";
		for (int i = 0; i < n; i++)
			cout << a[i] << " ";
		cout << "\n";
	};
	
	// print();
		
	SegmentTree st(n + 1);
	int best = 0, max_len = 0, len;
	
	for (int i = 0; i < n; i++) {
		Node qry = st.query(0, a[i] - 1);
		len = 1 + qry.val;
		if (len > max_len) {
			best = i;
			max_len = len;
		}
		prev[i] = qry.pos;
		st.update(a[i], len);
		max_len = max(max_len, len);
	}
	
	cout << best << "\n";
	for (int i = 0; i < n; i++)
		cout << prev[i] << " ";
	
	fout << max_len << "\n";
			
	vector<int> lis;
	lis.push_back(tmp[a[best] - 1]);
	best = prev[best];
	while (best != 0) {
		lis.push_back(tmp[a[best] - 1]);
		best = prev[best];
	}
	
	for (int i = (int)lis.size() - 1; i >= 0; i--)
		fout << lis[i] << " ";
	fout << "\n";
	
	fin.close();
	fout.close();	
	return 0;
}