## MINCOUNT - Move To Invert

no tags

A triangle made of coins of height h is as follows
It has h coins at the base and h-1 coins one level above base and so on.(Coins are placed as shown in the figure below)
And at the top most level there will be only one coin
Now given h the task is to invert this triangle by moving minimum number of coins. For example when h=4 triangle is

For h=4 at least 3 coins must be moved to invert it.

### Input

In the first line N will be given and then N lines follow with each line having a integer which is the height of triangle in that test case.00≤h<1010;

### Output

For each test case output in a seperate line the minimum number of moves required to invert the triangle. Output fits in long long data type

### Example

```Inputt:
1
3

Output:
2```

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>
#include <list>

using namespace std;

int main(){
int t=0;
scanf("%d",&t);
while(t--){
unsigned long long height;
scanf("%llu",&height);
if(height==0){
printf("0\n");
continue;
}/*
if(height==1){
printf("0\n");
continue;
}
if(height==2){
printf("1\n");
continue;
}*/
unsigned long long int ans=0;
height-=1;
long long num=height/3;
ans+=((num)*(num+1)/2)*3;
ans+=(num+1)*(height%3);
printf("%llu\n",ans);
}
return 0;
}``````
Copy The Code &

Input

cmd
1
3

Output

cmd
2

### #2 Code Example with Java Programming

```Code - Java Programming```

``````// Java program to count inversions
// in an array
class Test
{
static int arr[] =
new int[] {1, 20, 6, 4, 5};

static int getInvCount(int n)
{
int inv_count = 0;
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] > arr[j])
inv_count++;

return inv_count;
}

// Driver code
public static void main(String[] args)
{
System.out.println("Number of inversions are " +
getInvCount(arr.length));
}
}``````
Copy The Code &

Input

cmd
1
3

Output

cmd
2

## Demonstration

SPOJ Solution-MINCOUNT Move To Invert-Solution in C, C++, Java, Python,SPOJ Solution