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
Invert
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

hide comments
hunnychauhan: 2017-07-22 11:01:42

only formula required....might be weak test cases...

viratian_070: 2017-06-30 08:28:23

the moment u derive the formula....u get AC

rishabhjain996: 2016-08-26 20:04:40

dont forget n=0, caused me 2 wa :(

Utkarsh: 2016-02-06 05:57:03

observe the pattern

Nallagatla Manikanta: 2016-01-28 13:34:35

AC in one go :)

kapoor_adhish: 2015-12-17 15:43:10

nice problem

SangKuan: 2015-07-05 09:14:58

hard。

PRIBAN91: 2015-06-09 08:29:44

Getting lots of TLE in Java. Any suggestion will be appreciated.

Ankit Aggarwal : 2014-10-17 19:50:38

http://discuss.codechef.com/questions/50378/spoj-mincount-wa

Mahesh Mishra: 2014-10-17 08:37:51

Test Cases are weak..


Added by:Abhilash I
Date:2006-12-16
Time limit:0.325s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:IIIT Hyderabad Local Programming Contest