OHANIBTR - Ohani And Binary Search Tree

Ohani has recently learned about complete binary tree and binary search tree. Now she wants to create a complete binary tree and insert some value in the nodes such that it maintains the property of a binary search tree. She calls this tree Complete Binary Search Tree. So she takes a sorted array and one by one she inserts the values in a complete binary tree to create Complete Binary Search Tree (CBST).

A binary tree is called a Binary Search Tree if for each node u, the value of u is greater than every value in the left subtree of u and is less than every value in right subtree of u.

A binary tree is said to be complete if all its levels, expect possibly the last, have the maximum number of possible nodes, and if all the nodes at the last level appears as far left as possible. So, there is a unique complete tree for n nodes. Here is a complete tree of 10 nodes.

binary tree

Let a sorted array of five element is: 1 3 4 6 9. So, the CBST of this array is:

CBST

But suddenly she comes through a problem. Her teacher gave her an array which is unsorted. So, she first sort the array and then use the sorted array to create CBST. To sort the array, she takes any elements and place it at any place in the array in one step. For example: if an array is: 1 4 2 3, she can take 2 and place it after 1, she can then take 4 and place it after 3, so, total 2 steps sorts the array. But this is not the minimum. Now your task is to find the minimum number of steps needed to sort an unsorted array using Ohani's procedure and then build a CBST.

Input

The first line of the input contains an integer T (1<=5) denoting the number of test cases.

Each test case contains of two lines. First line contains an integer N (1 <= N <= 100000),  the number of elements in the array.
Next line contains N distinct numbers where each numbers will be between 1 to N.

Output

For each test case, you need to output the case number on  the first line.
In the second line you have to output the minimum numbers of steps required to sort the array.
In the third line, for each  value from 1 to N, the parent of these values in the built CBST. The parent of the root is -1.

For example, for if the given array is: 1 4 2 3, then the output for the CBST is,

2 3 -1 3

Because, the parent of value 1 is 2, the parent of value 2 is 3, 3 is the root, so, its parent is -1, the parent of 4 is 3.

Example

Input:
1
4
1 4 2 3

Output:
Case 1:
Minimum Move: 1
2 3 -1 3 

Added by:Raihat Zaman Neloy
Date:2014-10-16
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2016-04-02 17:09:29 Vivek Mangal
oh! this is disgusting. those who are getting WA,plz don't print space after the last number. For eg. 2 3 -1 3
then there is no space after 3(the last number).

Last edit: 2016-04-02 19:58:42
2015-01-11 14:36:45 VISHAL DEEPAK AWATHARE
what do you mean by no space??@kashish Mittal
2015-01-11 06:44:42 kancha
@Andy yeah i was getting wa cause of this.. :/ Thanks
2015-01-10 06:24:37 VISHAL DEEPAK AWATHARE
im getting some trouble during input, im using java , and trying bufferedreader.readline(), but dont know why its showing NZEC, only for reading the input

Last edit: 2015-01-10 06:25:03
2015-01-08 04:39:28 VISHAL DEEPAK AWATHARE
any hints on how to from CBST?
2014-11-15 18:49:35 Andy
there is no space after the last number
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.