浙大ACM1440 Bone Sort



WishingBone有许多骨分拣机，可以执行如下的功能：







有一天，他偶然发现他可以使用几个这样的骨分拣兴建超级骨分拣。例如，下面的数字说明了一个方法来建构水平的4超级骨分拣六个骨分拣机，可以进行排序4个任意数字。







但是，作为一个小狗，他是骨头确保节俭。于是，他想知道什么骨分拣机的数量最少可以构建一个n-超骨分拣。此外，他并不真正需要的一般的分拣，但他事先知道一些数字，这样你就可以采取这种优势，在计算解决方案。 （假设骨分拣机可以放在任何对线）。



顺便说一下，他也急切地想知道原号码的反演。 （他希望这个值来评价他的骨头分拣效率。）数反转（AI，AJ）等对满足我<j和Ai> AJ的。-WishingBone has many bone sorters that can perform function as follows:







One day he happened to find out he could use several such bone sorters to construct super bone sorters. For instance, the figure below illustrates one way to construct a level 4 super bone sorter with six bone sorters, which can sort 4 arbitrary numbers.







But, as a doggie, he is sure thrift on bones. So he wonders what the minimal number of bone sorters to construct an n-super bone sorter could be. Besides, he does not actually need a general sorter, but one on some numbers he knows in advance, so that you may take this advantage in calculating the solution. (Suppose bone sorter can be placed on any pair of lines.)



By the way, he is also eager to know the inversion number of the original numbers. (He wants this value to evaluate the efficiency of his bone sorter.) Inversion number is the number of such pairs (Ai, Aj) that satisfies i<j and Ai>Aj.