Initially there is a sorted array. Say, Initially array A was \n\n```\nA=  0   0   1   2   5   6   8   8   9  10 \ni=  0   1   2   3   4   5   6   7   8   9 \n```\nFollowing 3 operations are performed to obtain B from A\n\n1. Copy elements in even indices from A to B\n2. Split odd indices into two parts `left` and `right`. If there are odd number of odd indices ignore middle most odd number when computing `left` and `right` so that both have same number of odd numbers.\n3. For every odd index in `left`, swap it with some odd index in `right`. \nFor example, B can be \n```\nB= 0  10   1   8   5   |6|   8   2   9   0 \ni= 0   1   2   3   4   |5|   6   7   8   9 \n```\n(|| used to show left and right)\n`B` could also be \n\n```\nB= 0   8   1  10   5   |6|   8   0   9   2 \ni= 0   1   2   3   4   |5|   6   7   8   9 \n```\n\nSearch in this array B for key k.\n\nAnother simpler example,\n\n```\n  A= 0   1   2   3   4   |5|   6   7   8   9 \n  i= 0   1   2   3   4   |5|   6   7   8   9 \n\n```\n`B` can be \n\n```\n  B= 0   7   2   9   4   |5|   6   1   8   3 \n  i= 0   1   2   3   4   |5|   6   7   8   9 \n```\n or\n ```\nB= 0   9   2   7   4   |5|   6   3   8   1 \n i= 0   1   2   3   4   |5|   6   7   8   9 \n```\n

Initially there is a sorted array. Say, Initially array A was \n\n\nA=  0   0   1   2   5   6   8   8   9  10 \ni=  0   1   2   3   4   5   6   7   8   9 \n\nFo