NCLNE - Clones

no tags 

Trouble has befallen the ninja world (again!). As always, our hero Naruto has taken the responsibility to defend everyone from the evil forces. His signature attack is the cloning jutsu (i.e. cloning technique) in which he produces one clone of himself in one second. Each clone of Naruto can also perform the cloning technique.

Naruto arrives alone at the battlefield at t=1 second. At each time step , t= 1,2,3,….,n second , some of the Narutos will leave to start fighting the enemy and the rest will stay back and perform the cloning jutsu again. If a clone  has left to fight the enemy he cannot come back to perform the jutsu. Also at t=n seconds all Narutos will go to fight with the enemy, i. e. no more cloning will take place on and after n seconds. Naruto is a very dedicated ninja so he won’t allow any of his clone to stay out of the fight.
The commander of the ninja forces observes Naruto’s actions. He notes down the number of clones that went to fight the enemy at each time step( from t=1 second till t=n second).  However he is old and doubts if his observations are correct. He hires you, a ninja with sharp analytical skills, to check if his observations can be  valid or not.

INPUT:

The first line of the input contains t the number of test cases. The first line of each test case contains n, the time when all Naruto clones go to fight. In the second line of each test case there are n space separated integers that tell how many Naruto clones went to fight at successive seconds, starting from t = 1 second till t = n seconds;

OUTPUT:

For each test case output either “Yes” or “No” (without quotes) in a single line. “Yes” if the commander’s observations were correct and “No” if they were wrong;

CONSTRAINTS:

1<= T <= 20

1<= n <=10^6

Each of the n integers will be less than or equal to 2 ^ 30

SAMPLE TEST CASES:


INPUT:

3

3

0 0 4

2

0 5

3

0 1 2

OUTPUT:

Yes

No

Yes



EXPLANATION:

For the sample test case 2 :

2

0 5

At t = 1 second, Naruto population is 1. According to the commander’s observations no Naruto leaves to fight at t=1 ( and all will perform the cloning jutsu), so the population will become 1 X 2= 2. He observed that at t=2 seconds, 5 narutos went to fight. This is not possible as at t=2 seconds the Naruto population is only 2. Therefore, the commander’s observations are incorrect.

 


hide comments
sehgal_divij: 2017-09-08 12:55:00

Works locally, but fails on server. Can anyone help? I am using Python3

Last edit: 2017-09-08 13:00:10
vengatesh15: 2017-03-07 07:11:45

AC in 1 go:-)

sachinsharma12: 2017-01-21 16:30:38

Much easy than what i thinking..

cs_abhi2000: 2017-01-20 20:07:16

Easy...
AC in one go...

adichd123: 2016-07-09 11:14:19

too easy!!

sy_117: 2015-09-21 19:12:43

Easy one AC in one go ......

xMAn: 2015-09-18 16:42:29

not even tutorial stuff -_-

Rajat Singh: 2015-09-04 15:48:45

good simulation problem!!!!!be careful while reading...

dwij28: 2015-08-30 13:19:45

Easy, but take care of the last observation made by the old man.. :)

kartikay singh: 2015-08-25 04:03:44

I wonder how ppls are able to solve in 0.00s :P


Added by:Abhinav92003
Date:2013-10-05
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64