У финалу женске дивизије прошлогодишњег Отвореног првенства Сједињених Америчких Држава у тенису (познатијем у народу као Ју Ес Опен) састале су се Ема Радукану и Лејла Фернандез. Неки посвећенији обожаватељи су приметили да је најдужи меч који је играла Радукану на путу до финала (97 минута) био краћи од најкраћег меча који је одиграла Фернандез на путу до финала (105 минута). Цео тениски свет се сложио да је ова чињеница интересантна.

Ви тренутно организујете свој турнир са \(N+1\) кола, на ком се већ одиграло прво коло. Остало је још \(2^N\) играча, који су редом нумерисани бројевима \(1,2,3,\cdots,2^N\). Турнир је организован као комплетно бинарно стабло, а \(i\)-ти играч се налази у \(i\)-том листу тог стабла при стандардном (лево-корен-десно) обиласку, и у сваком мечу победник иде даље, док губитник отпада. По угледу на претходно наведено финале, ви сте одлучили да је меч интересантан ако је дужине барем као најдужи меч који је до сада играо играч са леве стране жреба (то јест онај са мањим индексом), а дужине највише најкраћег меча који је до сада играо играч са десне стране жреба (то јест онај са већим индексом).

Познате су вам дужине трајања свих мечева из првог кола, а баш циљ је да турнир буде што интересантији. За сваки меч потребно је да изаберете победника и дужину трајања, тако да буде максимално могуће интересантних мечева. Играчи ће се, наравно, сложити са вашим предлогом о дужини меча и победнику.

Описи функција

Потребно је да имплементирате функцију

• \(Interesantnost(N, A[\ldots])\)

где је \(N\) број кола које треба још одиграти, а \(A[\ldots]\) низ дужине \(2^N\) који представља дужине трајања мечева првог кола - први меч играча \(i\) је трајао \(A[i]\) минута. Низ је индексиран од 1.

Функција треба да врати највећи могући број интересантних мечева. ## Пример

Нека је \(N=2\), \(A=\{6,8,10,2\}\). Први меч се игра између играча чији су мечеви у првом колу трајали \(6\) и \(8\) минута, тако да тај меч мора трајати барем \(6\) а највише \(8\) минута да би био интересантан - нека је на пример трајао \(7\) минута, и нека је победио играч број \(2\). Други меч да би био интересантан, мора да траје барем \(10\) а највише \(2\) минута, тако да очито никада неће бити интересантан, нека је на пример у њему победио играч број \(4\) и да је меч трајао \(9\) минута. Сада, у финалу ће се срести играч \(2\) са леве стране жреба, чији је најдужи меч трајао \(8\) минута, и играч \(4\) са десен стране жреба, чији је најкраћу меч трајао \(9\) минута. Ако финале траје \(8\) минута, онда ће и оно бити интересантно тако да може бити највише \(2\) интересантна меча, па функција треба да врати \(2\). ## Ограничења

• \(1 \leq N \leq 20\)
• \(1 \leq А[i] \leq 10^9\)

Подзадаци

Тест примери су подељени у \(5\) подзадатка:

• [10 поена]: \(N\le4\).
• [17 поена]: \(A[i]\le2\).
• [18 поена]: \(N\le 17\) и \(A[i]\le100\).
  
• [26 поена]: \(N\le17\).
  
• [29 поена]: Нема додатних ограничења.

Детаљи имплементације

Потребно је да пошаљете тачно један фајл us_open.cpp који имплементира поменуту функцију. Осим тражене функције, ваш фајл може садржати и додатне глобалне променљиве, помоћне функције и додатне библиотеке.

Ваша функција мора бити следећег облика:

int Interesantnost(int N, int* A);

Вашим програмима је дозвољено да мењају садржај низова али не смеју да приступају ван граница датих низова.

Уз задатак, обезбеђен вам је “template” фајл code.cpp које можете користити и мењати по потреби. Такође вам је обезбеђен програм grader.cpp који служи да лакше тестирате кодове. Овај програм учитава са стандардног улаза следеће податке:

• У првом реду број \(N\).
• У наредном реду \(2^N\) бројева: \(A[i]\).

Затим овај програм зове вашу функцију и исписује резултат који ваша функција врати.