Недавно Поликарп стал сотрудником компании «Double Permutation Inc.» Теперь он фанатеет от перестановок и всюду их ищет!

Перестановкой в этой задаче будем называть такую последовательность целых чисел $$$p_1, p_2, \dots, p_k$$$, что каждое целое число от $$$1$$$ до $$$k$$$ встречается в ней ровно один раз. Например, следующие последовательности являются перестановками $$$[3, 1, 4, 2]$$$, $$$[1]$$$ и $$$[6, 1, 2, 3, 5, 4]$$$. Следующие последовательности не являются перестановками: $$$[0, 1]$$$, $$$[1, 2, 2]$$$, $$$[1, 2, 4]$$$ и $$$[2, 3]$$$.

В холле штаб-квартиры компании опубликована статистика посещения веб-сайта компании за последние $$$n$$$ дней — последовательность $$$a_1, a_2, \dots, a_n$$$. Поликарп хочет покрасить все элементы этой последовательности один из трёх цветов (красный, зеленый или синий) так, что:

• все красные числа, будучи выписанными из $$$a_1, a_2, \dots, a_n$$$ слева направо (то есть без изменения их относительного порядка), должны образовывать некоторую перестановку (назовём её $$$P$$$);
• все зеленые числа, будучи выписанными из $$$a_1, a_2, \dots, a_n$$$ слева направо (то есть без изменения их относительного порядка), должны образовывать туже самую перестановку $$$P$$$;
• среди синих чисел не должно быть элементов, которые равны некоторому элементу перестановки $$$P$$$.

Помогите Поликарпу покрасить все $$$n$$$ чисел так, чтобы суммарное количество красных и зеленых элементов было максимально.