[HackerEarth] There are N trucks that are participating at Independence day parade this year. Each truck is given a number. They go in the parade in the ascending order of those given numbers. In the - P15012

P15012 [HackerEarth] There are N trucks that are participating at Independence day parade this year. Each truck is given a number. They go in the parade in the ascending order of those given numbers. In the

普及

题目描述

There are N trucks that are participating at Independence day parade this year. Each truck is given a number. They go in the parade in the ascending order of those given numbers. In the morning of the parade day all the trucks arrive at a place from where they start. They might come in different order. So Jay has been assigned to arrange them in the order.

But unfortunately, Vinay, the person who allotted the numbers of ordering to the trucks is lazy enough to mess up things. He gave same number to multiple trucks. This surely makes Jay go mad off in ordering them. But believe in Jay. He makes the arrangement look good. He orders them in such a way that equal numbers are arranged in the sequence they are now in.

A truck can change from its current position to next position(Either front or back) in 1 minute. Imagine trucks are lying in a single lane and could pass through each other. Jay wants to find the minimum time it would take in arranging them.
Note that multiple trucks can change their position simultaneously.
Input Format:
First line contains T, number of test cases.
First line of every case contains a number(N) denoting number of Trucks that participate in parade.
Second line of every case contains N numbers(a1,a2,..ai,..aN) denoting the numbers of trucks they initially are arranged in.

Output Format:
Output the minimum time it takes to arrange the trucks as thought by Jay. Output of each case in a new line.

Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 10000
1 ≤ ai ≤ 10000

Problem Setter : Vinay Kumar

Large I/O files. Use scanf() and printf() instead of cin and cout

SAMPLE INPUT
2
6
5 6 2 1 8 2
5
5 8 21 6 4

SAMPLE OUTPUT
3
4

Explanation

Test Case 1 : Given are six trucks (a1,a2,a3,a4,a5,a6) with numbers (5,6,2,1,8,2) respectively. After arranging them in the order as mentioned above, the numbers would in order of 1 2 2 5 6 8 (denoting trucks a4, a3, a6, a1, a2, a5). It takes 3 minutes for a1 to reach this position, after which the arrangement is complete.

输入格式

见题面

输出格式

见题面

样例输入

68
87
4 26 18 62 59 25 19 29 18 77 72 32 87 53 31 55 74 74 66 6 73 79 69 18 6 2 17 32 57 46 13 52 63 22 26 35 38 44 55 55 25 39 78 17 84 21 63 70 87 41 68 72 33 49 81 30 50 2 61 19 48 73 63 15 86 1 41 36 37 1 82 61 39 73 69 27 85 45 2 76 85 69 60 22 22 54 51
100
33 61 77 69 40 13 27 87 95 40 96 71 35 79 68 2 98 3 18 93 53 57 2 81 87 42 66 90 45 20 41 30 32 18 98 72 82 76 10 28 68 57 98 54 87 66 7 84 20 25 29 72 33 30 4 20 71 69 9 16 41 50 97 24 19 46 47 52 22 56 80 89 65 29 42 51 94 1 35 65 25 15 88 57 44 92 28 66 60 37 33 52 38 29 76 8 75 22 59 96
30
8 16 14 9 9 4 22 19 10 27 5 14 14 24 9 27 11 5 29 19 19 10 28 18 7 15 4 1 24 21
100
73 26 45 91 6 40 55 87 70 83 43 65 98 8 56 5 49 12 23 29 100 44 47 69 41 23 12 11 6 2 62 31 79 6 21 37 45 27 23 66 9 17 83 59 25 38 63 25 1 37 53 100 80 51 69 72 74 32 82 31 34 95 61 64 100 82 100 97 60 74 14 69 91 96 27 67 85 41 91 85 77 43 37 8 46 57 80 19 88 13 49 73 60 10 37 11 43 88 7 2
14
7 12 10 14 14 6 3 10 4 5 4 4 7 2
51
37 14 1 35 50 21 24 17 46 45 32 19 24 33 38 10 36 11 8 27 15 36 3 42 49 24 6 13 25 44 16 35 6 41 18 30 10 42 46 29 35 26 21 32 8 8 15 17 18 47 17
55
42 10 30 53 8 52 50 37 28 54 39 55 33 19 34 54 22 54 44 4 9 44 44 24 26 30 3 37 34 25 31 7 34 48 5 41 44 54 9 3 39 48 2 16 53 22 1 19 8 45 22 16 20 52 26
5
4 3 1 4 2
3
3 1 2
44
12 23 29 32 37 34 44 3 4 28 36 15 24 21 24 32 1 10 18 37 30 18 40 44 18 37 43 24 30 42 44 41 21 28 4 33 38 3 35 17 30 2 7 29
62
51 29 56 8 32 32 48 47 20 59 6 46 29 35 49 5 30 21 45 10 3 33 55 5 45 35 27 51 13 29 38 61 55 32 7 24 61 52 6 16 48 9 59 13 42 45 15 9 2 57 16 2 25 8 4 7 40 28 55 51 57 29
85
47 68 52 41 10 63 16 55 53 49 46 64 64 44 29 78 40 64 28 29 53 20 32 85 76 45 39 69 11 4 5 14 28 57 54 79 76 70 48 85 75 9 63 10 9 48 2 48 68 71 33 77 48 21 77 38 65 72 63 32 32 67 3 16 80 56 9 71 82 57 27 28 22 5 37 30 9 81 34 77 66 23 68 70 43
86
67 69 83 74 74 36 46 35 12 80 64 83 63 61 75 14 84 64 35 34 36 61 26 48 28 85 54 7 38 19 8 11 1 5 76 75 32 35 15 44 29 78 40 83 53 20 10 50 83 36 83 24 11 15 71 30 13 30 28 42 48 36 52 41 40 42 21 71 68 35 20 2 27 51 85 79 70 86 34 58 28 22 81 30 36 57
69
30 43 42 37 3 53 60 29 69 53 64 4 22 56 19 18 42 1 40 22 58 6 5 59 43 9 57 59 6 43 50 7 57 62 14 30 45 4 58 44 57 23 19 49 9 37 37 22 8 8 43 36 13 48 26 26 27 13 55 3 26 35 9 53 28 22 13 43 66
66
58 62 27 64 11 66 26 20 54 36 40 55 63 26 19 13 49 49 53 10 13 49 12 7 30 10 66 51 19 11 23 8 4 49 5 12 46 30 29 31 66 1 20 60 26 38 6 9 21 56 16 31 38 27 35 1 34 34 52 51 42 8 58 45 54 63
82
72 50 51 22 67 31 43 60 48 25 51 16 71 58 18 55 28 62 69 14 14 57 49 62 18 38 37 25 38 9 46 29 59 16 50 43 48 13 23 14 39 75 31 27 51 50 81 80 30 67 11 45 43 62 24 61 19 62 3 58 71 50 4 47 66 56 9 31 68 33 46 24 26 79 52 78 46 52 75 77 36 5
89
57 28 75 40 75 32 88 28 34 37 45 80 20 26 32 83 75 25 17 84 67 5 64 42 75 53 8 31 18 43 67 7 71 52 46 78 16 44 38 49 14 82 61 33 18 4 26 25 50 65 41 27 69 15 1 76 67 30 18 18 5 17 24 75 68 3 85 17 68 34 65 81 26 59 47 66 84 72 1 44 47 64 70 49 78 3 35 56 32
62
4 24 9 27 35 37 14 5 2 25 39 21 8 32 14 39 15 22 43 35 9 29 59 48 27 34 49 45 27 32 58 30 56 5 54 26 41 6 28 40 28 5 60 35 34 12 10 48 31 52 18 40 18 13 23 43 46 8 25 8 37 18
41
29 9 3 28 2 2 14 2 8 9 11 24 16 5 17 10 1 30 10 34 9 6 29 5 26 21 34 36 6 5 16 35 13 19 21 17 22 34 20 30 3
17
14 7 13 13 7 17 8 9 15 17 12 9 9 15 13 12 4
94
74 17 14 35 16 28 61 63 29 51 38 49 82 61 5 89 61 44 22 23 89 26 23 54 56 76 61 57 2 63 10 76 79 49 16 94 76 8 89 36 58 32 85 71 25 21 66 17 64 19 40 85 44 88 44 32 69 36 88 2 4 29 77 15 9 24 40 84 31 60 52 21 24 68 91 48 88 88 64 57 13 35 73 82 54 48 19 28 83 38 30 19 66 38
35
5 31 6 28 19 10 11 8 8 8 8 35 16 11 1 10 17 18 10 9 32 8 27 18 26 34 30 17 4 4 23 21 11 28 13
100
52 90 87 54 27 49 95 37 7 8 93 18 65 22 21 81 67 95 55 24 38 34 85 18 13 32 18 10 66 57 9 70 46 96 23 72 96 70 60 2 77 53 72 41 26 44 73 92 90 28 67 79 13 51 97 25 34 14 87 100 71 95 69 16 42 43 40 38 64 99 91 40 3 14 32 29 58 5 72 47 84 39 26 96 41 22 73 27 35 59 26 57 53 46 73 47 40 12 84 4
62
2 15 35 20 45 31 59 31 10 25 24 46 28 17 59 1 1 31 60 43 38 18 24 49 46 32 28 27 55 31 51 56 46 23 11 26 51 5 56 60 30 15 42 55 31 38 54 30 4 51 10 41 6 31 27 50 60 52 12 50 19 62
62
62 22 52 25 10 57 16 6 22 30 45 14 58 18 5 25 21 53 33 61 59 61 23 44 59 10 55 46 28 55 25 27 12 13 49 22 7 2 25 28 29 7 39 25 24 42 49 44 32 17 40 26 16 60 7 12 5 60 55 33 52 16
85
34 68 54 44 31 16 77 30 11 58 36 58 19 80 35 39 85 35 2 20 11 1 81 67 16 52 18 82 25 50 3 15 32 56 16 19 29 7 48 39 22 41 53 82 35 44 36 34 78 37 11 3 80 6 26 52 14 1 5 80 50 7 9 39 63 24 57 48 73 20 43 51 60 10 47 51 10 82 85 3 76 52 47 27 14
38
4 34 15 22 3 27 12 11 20 28 33 5 26 9 21 21 17 1 36 11 8 1 28 22 7 15 7 33 30 2 24 33 35 16 32 37 5 21
76
24 11 20 28 74 44 26 73 22 42 48 48 66 64 75 49 70 51 72 5 20 73 28 68 48 22 61 62 64 6 49 27 32 68 71 45 51 20 41 12 62 29 60 51 16 74 39 26 65 50 30 8 47 73 76 34 18 76 19 21 21 68 48 52 75 58 21 66 17 1 1 2 45 60 68 61
22
13 8 22 12 11 19 16 1 14 13 7 22 2 9 16 19 22 6 21 3 12 8
54
12 53 21 35 50 5 5 33 13 38 16 36 2 29 30 28 46 22 40 33 35 13 35 47 26 50 36 23 9 25 36 36 23 18 32 19 22 52 13 50 35 45 48 52 35 39 42 42 6 27 21 3 39 17
13
12 12 13 9 6 11 7 13 2 9 11 6 6
74
64 6 15 60 55 26 20 31 23 33 67 68 31 15 40 35 19 68 40 61 8 71 3 27 32 19 74 48 62 18 39 51 23 53 14 56 57 33 64 5 65 56 50 22 48 68 34 67 61 74 31 69 70 33 73 5 29 50 52 16 67 69 44 68 47 57 49 7 67 38 64 58 72 17
43
17 39 41 22 38 14 7 12 25 4 31 11 35 43 4 22 9 31 12 39 12 13 35 14 7 27 14 3 9 14 18 17 2 15 39 31 21 2 42 2 41 21 12
58
17 45 28 52 3 48 57 10 25 31 23 34 36 25 46 24 17 30 2 25 19 43 47 29 43 45 23 17 6 32 24 22 10 43 7 13 25 6 14 49 28 28 24 5 52 3 28 10 24 29 27 42 6 7 13 48 44 35
34
15 26 15 10 2 3 9 18 1 6 25 1 5 6 4 5 3 8 10 8 9 14 20 9 29 11 7 34 6 29 31 20 21 19
31
13 30 29 14 10 27 2 18 25 22 12 2 22 11 21 21 10 25 27 3 7 18 14 24 12 9 31 6 12 14 12
34
7 14 24 2 11 34 6 5 15 14 10 6 11 25 4 8 19 30 30 15 32 23 3 13 11 4 13 27 15 16 4 29 3 1
40
11 36 16 11 22 7 11 3 29 39 25 20 39 14 25 35 10 32 18 26 18 17 23 35 33 6 36 31 26 33 10 28 28 17 39 2 23 1 4 3
39
20 21 21 22 24 31 6 9 23 7 4 8 35 33 10 26 18 11 32 30 28 22 21 6 30 16 27 11 16 23 1 36 4 10 7 28 29 12 25
90
75 80 27 9 43 55 37 26 14 55 88 5 58 22 45 81 85 9 34 14 85 47 62 86 26 75 57 27 20 27 88 56 17 25 64 21 41 63 46 54 79 6 21 46 27 27 88 74 35 31 49 81 39 72 76 64 56 42 52 75 31 12 2 9 36 28 29 76 52 37 1 40 42 73 85 30 61 82 65 5 74 23 86 22 4 33 47 21 37 60
37
19 14 9 33 15 20 37 6 14 28 3 11 35 31 23 26 6 2 31 7 12 7 19 11 36 2 10 22 13 17 31 31 9 2 26 23 36
45
1 37 38 23 39 6 34 35 18 9 29 5 3 13 21 36 18 40 19 31 42 38 7 11 2 22 44 40 7 28 22 14 26 14 43 20 26 32 16 44 2 7 3 4 19
63
56 8 33 11 56 57 47 15 29 19 27 7 21 23 52 51 27 49 10 52 23 35 63 27 33 28 24 24 57 32 26 49 39 59 57 29 50 38 44 13 57 5 19 14 27 6 1 54 54 10 40 11 42 39 37 12 1 61 33 57 27 59 40
59
56 20 15 2 19 42 10 49 22 26 7 55 19 52 47 6 13 2 50 47 37 18 21 13 38 38 54 22 8 44 47 8 8 6 13 26 48 22 16 14 52 26 13 11 19 5 21 35 6 11 26 43 32 50 55 14 29 53 39
84
23 47 82 38 68 46 78 75 39 53 25 74 79 53 72 31 60 24 17 47 22 58 66 17 41 36 48 35 13 55 58 76 18 11 29 41 57 22 31 51 74 11 40 69 19 67 55 79 47 27 41 68 1 62 40 81 13 3 31 65 58 44 56 31 11 41 71 23 18 57 73 48 23 68 32 41 6 42 35 52 25 31 75 25
44
15 29 28 25 31 25 34 38 16 20 8 28 42 38 10 30 26 33 28 17 4 5 7 5 11 2 9 18 29 37 5 43 41 33 43 3 33 9 41 4 28 24 8 26
10
9 5 1 9 1 6 10 1 10 2
49
33 25 37 1 20 35 46 27 3 26 32 2 42 1 36 31 35 34 29 36 22 6 11 3 25 49 46 27 46 48 34 30 28 22 35 47 7 32 29 14 13 12 20 5 17 11 40 2 45
45
22 31 3 9 5 9 17 24 12 45 28 43 22 44 34 5 39 4 12 7 9 1 30 39 35 30 23 15 22 45 1 6 30 3 21 41 18 37 20 29 36 9 33 19 8
49
28 19 35 33 7 12 2 12 7 28 38 13 45 11 14 37 31 37 14 49 34 44 21 8 11 45 16 42 5 25 25 37 43 15 20 5 26 21 21 33 5 9 45 5 25 10 42 6 2
61
60 18 46 14 29 9 43 55 16 59 36 5 56 8 15 58 12 48 38 37 33 13 20 28 18 59 47 48 50 34 16 50 53 61 4 20 9 48 15 24 46 52 31 42 59 47 38 12 33 15 48 5 27 8 34 46 6 21 32 57 56
78
24 54 73 47 71 7 63 65 40 69 75 69 4 22 1 30 35 23 1 34 67 43 1 37 43 26 43 7 11 13 12 34 17 6 30 9 13 14 23 52 33 19 42 64 41 70 15 75 14 16 59 31 8 9 67 50 34 60 6 44 22 17 27 38 23 56 46 63 19 19 64 51 37 27 36 27 46 1
38
29 2 22 35 27 2 14 18 35 11 30 34 20 4 20 10 28 19 15 8 3 21 9 16 34 3 9 32 32 17 19 1 34 18 35 22 35 26
80
61 48 27 40 54 4 77 5 50 29 15 27 80 30 68 19 61 52 5 74 76 50 45 44 79 66 16 63 9 24 22 69 23 48 61 76 3 57 32 52 38 79 79 37 28 18 55 40 21 11 33 48 12 77 43 11 15 59 73 23 34 14 43 8 13 55 36 15 32 67 19 21 65 49 9 44 66 63 35 38
45
13 1 42 31 18 32 5 38 31 19 38 14 4 41 6 33 41 27 26 32 22 6 39 30 9 44 7 3 44 17 33 11 17 36 41 41 29 8 34 14 33 26 27 36 21
69
64 32 51 26 35 61 60 19 52 27 2 69 45 24 64 30 62 29 54 35 24 55 64 37 59 39 60 31 40 3 28 34 35 49 30 40 11 20 58 63 47 30 62 62 25 56 22 57 55 6 22 9 60 56 17 20 26 7 50 36 49 48 69 54 27 69 24 38 20
18
5 16 2 4 8 14 2 6 1 2 18 3 8 2 16 9 12 9
9
2 8 3 8 5 9 2 2 3
7
4 4 4 4 5 5 2
73
17 61 5 12 39 46 2 3 26 51 2 25 22 16 50 15 1 14 11 5 37 51 20 60 53 62 72 15 6 58 57 22 45 61 18 67 33 19 53 42 69 54 66 1 53 27 15 53 24 10 41 44 44 60 30 23 33 28 22 38 12 5 43 40 49 60 17 65 62 69 33 42 33
43
34 40 35 42 29 13 6 38 11 2 23 3 4 36 26 2 14 33 33 36 7 21 8 19 36 34 35 34 2 26 15 36 14 41 26 42 10 31 28 12 24 7 14
39
17 27 5 33 34 15 29 33 16 2 37 4 24 18 13 18 39 7 2 16 19 8 26 14 14 19 19 31 16 3 15 33 30 19 26 13 23 4 7
82
56 63 72 56 44 7 41 61 77 50 33 62 9 30 63 76 79 46 62 48 40 21 36 6 67 72 78 38 29 5 3 4 67 76 61 30 82 21 9 79 70 41 58 78 70 38 73 67 3 53 34 43 73 71 50 57 60 45 14 8 51 19 12 38 12 74 67 14 13 75 10 2 33 67 82 23 25 72 9 29 42 42
95
31 30 12 34 23 42 10 53 84 51 31 11 63 73 24 76 63 14 16 35 34 31 8 32 94 19 28 50 13 78 62 43 12 73 73 32 19 82 81 4 34 13 11 94 85 35 74 50 48 87 84 78 19 91 15 14 14 42 60 23 22 26 65 30 95 43 61 16 26 46 19 57 58 27 55 45 61 30 94 10 18 79 87 33 74 3 46 84 42 8 12 63 30 73 92
55
12 35 27 25 35 50 31 45 31 7 41 8 33 54 4 33 4 48 47 17 42 40 32 23 37 25 2 51 38 29 47 36 8 18 5 29 55 22 5 17 28 45 12 48 30 15 12 33 49 3 36 23 42 13 45
78
16 76 55 11 61 55 1 33 60 73 6 3 78 65 1 3 3 59 23 9 59 13 44 17 55 72 57 69 37 54 23 2 1 27 13 61 3 41 43 12 35 48 14 62 62 15 15 65 23 37 73 3 78 66 48 4 59 26 72 17 1 44 19 1 70 59 11 23 21 53 34 5 51 48 67 34 12 31
48
26 41 12 3 46 6 32 25 26 19 29 11 8 18 21 12 38 13 15 12 37 43 9 5 1 36 3 5 27 21 40 21 14 20 23 27 25 22 20 18 40 48 28 15 17 48 43 6
96
9 81 16 19 10 85 68 45 87 24 40 76 31 12 9 2 50 51 90 71 70 12 14 69 55 45 6 55 39 27 2 47 76 82 65 85 70 36 1 28 27 8 71 58 19 79 27 68 2 21 10 71 32 24 12 86 68 81 12 10 75 14 24 54 95 88 42 36 28 11 63 22 18 6 79 5 52 10 40 53 94 50 28 29 41 7 82 76 87 62 53 65 43 76 23 9

样例输出

题目信息

时间限制	2000 ms
内存限制	256 MB
难度	普及
提交数	0
通过数	0
通过率	0.0%

登录后 AI 解题查看题解登录后提交