Minimum time to finish tasks without skipping two consecutive

PROBLEM :

Given an array A[ ] denoting the time taken to complete N tasks, determine the minimum amount of time required to finish the tasks considering that you can skip any task, but skipping two consecutive tasks is forbidden.


For example
For the array arr [] = {10, 5, 2, 4, 8, 6, 7, 10}
the output will be  22  (Skip the tasks taking more time ,avoiding consective skipping(10,8,10). Tasks done in: 5+2+4+6+7)


Input
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow.
The first line of each test case contains a positve integer N, denoting the length of the array A[ ].
The second line of each test case contains a N space seprated positve integers, denoting the elements of the array A[ ].


Output
Print out the minimum time taken to complete the tasks.


Constraints
1 <= T <= 100
0 <   N <= 30
0 <= A[ ] <= 1000


Examples

Input
4
4
10 5 7 10
6
5 6 7 8 9 10
2
10 20
5
22 10 15 3 5

Output
12
21
10
13


Expected Complexity
Time: O(N)
Space: O(1)

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;
int Skip_the_work(int [],int ) ;
int min(int ,int ) ;
int main()
 {
int t,no,arr[1000],i ;
cin>>t ;
while(t--)
{
   cin>>no ;
   for(i=0;i<no;i++)
       cin>>arr[i] ;
     
   no=Skip_the_work(arr,no) ;
   cout<<no<<endl ;
}
return 0;
}

int Skip_the_work(int arr[],int no)
{
    int a,b,c,d,i ;
    if(no==0||no==1)
        return 0 ;
       
    a=arr[0] ;
    b=0 ;
   
    for(i=1;i<no;i++)
    {
        c=arr[i]+min(a,b) ;
        d=a ;
       
        a=c ;
        b=d ;
    }
    return min(a,b) ;
}

int min(int a,int b)
{
    return a<b?a:b ;
}

--------------------------------------------------------------------------------
BETTER c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;
int Skip_the_work(int [],int ) ;
int min(int ,int ) ;
int main()
 {
int t,no,arr[1000],i ;
cin>>t ;
while(t--)
{
   cin>>no ;
   for(i=1;i<=no;i++)
       cin>>arr[i] ;
     
   no=Skip_the_work(arr,no) ;
   cout<<no<<endl ;
}
return 0;
}

int Skip_the_work(int arr[],int no)
{
    int a,i ;
   
    a=arr[0] ;
   
    for(i=2;i<=no;i++)
    {
        arr[i]=arr[i]+min(arr[i-1],arr[i-2]) ;
    }
    return min(arr[no],arr[no-1]) ;
}

int min(int a,int b)
{
    return a<b?a:b ;
}

---------------------------------------------------------------------------------