У вас есть граф с $$$2^{n + 1} - 1$$$ вершинами. Граф является полным двоичным деревом — другими словами, между вершинами с номерами $$$i$$$ и $$$\lfloor\frac{i}{2}\rfloor$$$ для всех $$$i$$$ от $$$2$$$ до $$$2^{n + 1} - 1$$$ проведено ребро. На каждом ребре лежит так называемый D-mail с мощностью $$$0$$$, $$$1$$$ или $$$2$$$.
Если вкратце, то D-mail с мощностью $$$x$$$ позволит вам переместиться во времени из $$$(11 - x)$$$-го октября на один день назад, в $$$(11 - x - 1)$$$-е октября. Например, имея хотя бы один D-mail с мощностью $$$0$$$, вы сможете переместиться в $$$10$$$-е октября, а, имея D-mail-ы с мощностями $$$0$$$ и $$$1$$$, можно попасть аж в $$$9$$$-е октября, в то время как один D-mail с мощностью $$$1$$$ сам по себе не позволит вам никуда переместиться.
Чтобы успеть подготовиться к отбору на ЧеРеКОШ, вы хотите переместиться из $$$11$$$-го октября в прошлое. Для этого вы можете один раз выбрать любые две вершины в дереве, забрать все D-mail-ы, лежащие на кратчайшем пути между этими вершинами, и использовать их по своему усмотрению в любом порядке.
Вы хотите выбрать вершины таким образом, чтобы полученные D-mail-ы позволили вам переместиться как можно дальше в прошлое. Если таких способов взять вершины много, то вам нужно выбрать из них вариант, при котором расстояние между взятыми вершинами минимально. Определите, как это сделать.
В первой строке входных данных содержится одно целое число $$$n$$$ ($$$1 \le n \le 18$$$) — глубина дерева.
Во второй строке входных данных содержится $$$(2^{n + 1} - 2)$$$ целых чисел $$$a_2, a_3, a_4, \ldots, a_{2^{n + 1} - 1}$$$ ($$$0 \leq a_i \leq 2$$$), где $$$a_i$$$ — мощность D-mail-а, лежащего на ребре между вершинами $$$i$$$ и $$$\lfloor\frac{i}{2}\rfloor$$$.
В единственной строке выходных данных выведите два целых числа через пробел — на сколько дней в прошлое вы сможете переместиться и кратчайшее расстояние между вершинами, которые вы можете для этого выбрать.
10 0
1 1
21 0 0 1 2 0
3 3
11 2
0 0
В первом примере из условия граф выглядит следующим образом:
Чтобы переместиться в $$$10$$$-е октября, можно выбрать пару вершин $$$(1, 2)$$$, $$$(1, 3)$$$ или $$$(2, 3)$$$. Для пар $$$(1, 2)$$$ и $$$(1, 3)$$$ расстояние между вершинами равно $$$1$$$, для $$$(2, 3)$$$ — $$$2$$$, поэтому ответ — $$$1$$$ $$$1$$$.
Во втором примере из условия граф выглядит следующим образом:
Чтобы переместиться на три дня, можно выбрать пару вершин $$$(4, 6)$$$, $$$(5, 6)$$$ или $$$(2, 6)$$$. Кратчайшее расстояние между вершинами имеет пара $$$(2, 6)$$$.
В третьем примере из условия мы не сможем переместиться в прошлое ни на один день, как бы мы ни выбирали пару вершин. Чтобы получить кратчайшее расстояние $$$0$$$, достаточно выбрать пару из двух одинаковых вершин: $$$(1, 1)$$$, $$$(2, 2)$$$ или $$$(3, 3)$$$.