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

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
Mayank Garg: 2015-08-03 23:28:40

3 wa's due to silly mistakes >:( printing "YES / NO" instead of "Yes/No" .. :p ... 0.20 for just knowing subtraction and multiplication.. :D

anuveshkothari: 2015-07-26 19:12:02

its like 0.2 are awarded for free..
simple multiplication and subtraction.

Anubhav Balodhi : 2014-03-14 09:20:05

Ac with simulation, tajuu kage bunshin no jutsu, Daattebayo ^_^
100th ;-D

Last edit: 2014-03-14 10:01:46
Ouditchya Sinha: 2014-02-20 11:04:04

@shivang : Read the question carefully, that's the catch(the answer "No" in that case). All the best! :)

shivang: 2014-01-14 17:41:59

@ouditchya sinha
why is the answer of your test case "no"...shouldnt it be "yes"??
see the first test case,pls....

J_P: 2014-01-09 13:58:58

finally ac... :)
try dis one:
1
1
ans:Yes....:)

Last edit: 2014-01-09 13:59:17
JordanBelfort: 2013-12-29 11:32:48

tutorial stuff.

Ouditchya Sinha: 2013-12-22 13:20:26

For those getting wrong answer, consider this-
3
0 0 3
Answer is No. All the best. :)

innovolt: 2014-05-21 23:12:29

easy one but take care of 1 case (clearly mentioned in ques bt many of us ignore)....


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