Mortal Kombat Tower SOLUTION
You and your companion are playing the game Mortal Kombat XI. You are attempting to pass a test tower. There are n managers in this pinnacle, numbered from 1 to n. The sort of the I-th manager is ai. On the off chance that the I-th manager is simple, at that point its sort is ai=0, in any case this supervisor is hard and its sort is ai=1.
During one meeting, possibly you or your companion can murder a couple of managers (neither you nor your companion can avoid the meeting, so the base number of supervisors slaughtered during one meeting is in any event one). After your companion meeting, your meeting starts, of course your companion meeting starts, your meeting starts, etc. The main meeting is your companion’s meeting.
Your companion needs to get great since he can’t really murder hard managers. To execute them, he utilizes skip focuses. One skip point can be utilized to murder one hard chief.
Your undertaking is to locate the base number of skip focuses your companion needs to utilize so you and your companion execute all n managers in the provided request.
For instance: assume n=8, a=[1,0,1,1,0,1,1,1]. At that point the best strategy is the accompanying:
your companion executes two first managers, utilizing one skip point for the primary chief;
you execute the third and the fourth supervisors;
your companion executes the fifth chief;
you execute the 6th and the seventh supervisors;
your companion executes the last chief, utilizing one skip point, so the pinnacle is finished utilizing two skip focuses.
You need to answer t autonomous experiments.
The primary line of the info contains one number t (1≤t≤2⋅104) — the quantity of experiments. At that point t experiments follow.
The principal line of the experiment contains one number n (1≤n≤2⋅105) — the quantity of supervisors. The second line of the experiment contains n numbers a1,a2,… ,a (0≤ai≤1), where ai is the sort of the I-th chief.
It is ensured that the whole of n doesn’t surpass 2⋅105 (∑n≤2⋅105).
For each experiment, print the appropriate response: the base number of skip focuses your companion needs to utilize so you and your companion murder all n managers in the provided request.
1 0 1 0 1
1 0 1
We are Live Join Us
Check Your Mails