Problem 863C : Restore The Array || Full Detailed Solution || Codeforces

Question :

Kristina had an array 

a$�$ of length n$�$ consisting of non-negative integers.

She built a new array b$�$ of length n−1$�-1$, such that bi=max(ai,ai+1)${�}_{�}=max({�}_{�},{�}_{�+1})$ (1≤i≤n−1$1\le �\le �-1$).

For example, suppose Kristina had an array a$�$ = [3,0,4,0,5$3,0,4,0,5$] of length 5$5$. Then she did the following:

1. Calculated b1=max(a1,a2)=max(3,0)=3${�}_1=max({�}_1,{�}_2)=max(3,0)=3$;
2. Calculated b2=max(a2,a3)=max(0,4)=4${�}_2=max({�}_2,{�}_3)=max(0,4)=4$;
3. Calculated b3=max(a3,a4)=max(4,0)=4${�}_3=max({�}_3,{�}_4)=max(4,0)=4$;
4. Calculated b4=max(a4,a5)=max(0,5)=5${�}_4=max({�}_4,{�}_5)=max(0,5)=5$.

As a result, she got an array b$�$ = [3,4,4,5$3,4,4,5$] of length 4$4$.

You only know the array b$�$. Find any matching array a$�$ that Kristina may have originally had.

Input

The first line of input data contains a single integer t$�$ (1≤t≤104$1\le �\le {10}^4$) — the number of test cases.

The description of the test cases follows.

The first line of each test case contains one integer n$�$ (2≤n≤2⋅105$2\le �\le 2\cdot {10}^5$) — the number of elements in the array a$�$ that Kristina originally had.

The second line of each test case contains exactly n−1$�-1$ non-negative integer — elements of array b$�$ (0≤bi≤109$0\le {�}_{�}\le {10}^9$).

It is guaranteed that the sum of n$�$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$, and that array b$�$ was built correctly from some array a$�$.

Output

For each test case on a separate line, print exactly n$�$ non-negative integers — the elements of the array a$�$ that Kristina originally had.

If there are several possible answers — output any of them.

Example

input

Copy

11
5
3 4 4 5
4
2 2 1
5
0 0 0 0
6
0 3 4 4 3
2
10
4
3 3 3
5
4 2 5 5
4
3 3 3
4
2 1 0
3
4 4
6
8 1 3 5 10

output

Copy

3 0 4 0 5
2 2 1 1
0 0 0 0 0
0 0 3 4 3 3
10 10
3 3 3 1
4 2 2 5 5
3 3 3 3
2 1 0 0
2 4 4
8 1 1 3 5 10

 Explanation : 

b[1], min(b[1], b[2]), min(b[2], b[3]), ..., min(b[n-2], b[n-1]), b[n-1] is an answer.

Solution :

/* Deepak Yadav */

#pragma GCC optimize("O3,unroll-loops")

#include<bits/stdc++.h>

#include<ext/pb_ds/assoc_container.hpp>

#include<ext/pb_ds/tree_policy.hpp>

using namespace std;

using namespace chrono;

using namespace __gnu_pbds;

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

#define MOD 1000000007

#define MOD1 998244353

#define INF 1e18

#define nline "\n"

#define pb push_back

#define ppb pop_back

#define mp make_pair

#define ff first

#define ss second

#define PI 3.141592653589793238462

#define set_bits(x) __builtin_popcountll(x)

#define sz(x) ((int)(x).size())

#define all(x) (x).begin(), (x).end()

#define test     long long T;cin>>T;while(T--)

//#define ll             long long

#define fl(x, n) for (int x = 0; x < n; ++x)

#define cina(a, n) for(int i=0;i<n;i++){cin>>a[i];}

#ifdef Priyansh31dec

#define debug(x) cerr << #x<<" "; _print(x); cerr << endl;

#else

#define debug(x);

#endif

typedef long long ll;

typedef unsigned long long ull;

typedef long double lld;

typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update > pbds; // find_by_order, order_of_key

void _print(ll t) {cerr << t;}

void _print(int t) {cerr << t;}

void _print(string t) {cerr << t;}

void _print(char t) {cerr << t;}

void _print(lld t) {cerr << t;}

void _print(double t) {cerr << t;}

void _print(ull t) {cerr << t;}

bool Campare(const auto a, const auto b){

     if(a.first==b.first) return a.second<b.second;

     return a.first>b.first;

}

bool prime[1000001];

#define int    long long int

int divisor(int n){

  int cnt=0;

  for(int i=1;i<=n;i++){

     if(n%i==0) cnt++;

  }

  return cnt;

}

void solve(){

    //1811 C

    int n; cin>>n; vector<int> a(n-1), b(n);

    for(int i=0;i<n-1;i++)

       cin>>a[i];

    b[0]= a[0]; b[n-1]= a[a.size()-1];

    for(int i=0;i<n-2;i++)

        b[i+1] = min(a[i],a[i+1]);

    for(int i=0;i<n;i++)

        cout<<b[i]<<" ";

    cout<<endl;

}

signed main() {

#ifdef deepakyadav123

    freopen("Error.txt", "w", stderr);

#endif

    fastio();

    auto start1 = high_resolution_clock::now();

    test

    solve();

    auto stop1 = high_resolution_clock::now();

    auto duration = duration_cast<microseconds>(stop1 - start1);

#ifdef deepakyadav123

    cerr << "Time: " << duration . count() / 1000 << endl;

#endif

}

I Hope you liked it please tell me the suggestion in the comment below what shoud I change according to you.

And discuss the Approach in comment section if you want. share the solution with you frnds too.