arrays - Minimum elements in all contiguous subarrays -

i saw question asked find minimum of contiguous subarrays. eg. array a=[1,2,3], answer array b containing [1,2,3,1,2,1].
how -

b[0] = 1 subarray a[0]   b[1] = 2 subarray a[1]   b[2] = 3 subarray a[2]   b[3] = 1 subarray a[0,1]   b[4] = 2 subarray a[1,2]   b[5] = 1 subarray a[0,1,2] 

what did, is, constructed segment tree, doesn't contains minimum of contiguous subarrays.
don't think can use "dequeues" either, because don't have find min in subarray of particular length.
so, how can min. of contiguous subarrays(that b array)?

here implementation using segment tree:

#include <stdio.h> #include <math.h> #include <limits.h> #include <iostream>  using namespace std;  int mid(int s, int e) {  return s + (e -s)/2;  } int rmqutil(int *st, int ss, int se, int qs, int qe, int index) {     if (qs <= ss && qe >= se)         return st[index];     if (se < qs || ss > qe)         return int_max;      int mid = mid(ss, se);     return min(rmqutil(st, ss, mid, qs, qe, 2*index+1),                   rmqutil(st, mid+1, se, qs, qe, 2*index+2)); } int rmq(int *st, int n, int qs, int qe) {     if (qs < 0 || qe > n-1 || qs > qe)     {         printf("invalid input");         return -1;     }      return rmqutil(st, 0, n-1, qs, qe, 0); } int constructstutil(int arr[], int ss, int se, int *st, int si) {     if (ss == se) {         st[si] = arr[ss];         return arr[ss];     }     int mid = mid(ss, se);     st[si] =  min(constructstutil(arr, ss, mid, st, si*2+1),                      constructstutil(arr, mid+1, se, st, si*2+2));     return st[si]; } int *constructst(int arr[], int n) {     // allocate memory segment tree     int x = (int)(ceil(log2(n)));     int max_size = 2*(int)pow(2, x) - 1;     int *st = new int[max_size];      // fill allocated memory st     constructstutil(arr, 0, n-1, st, 0);     return st; } int main() {     int arr[] = {1, 2, 3};     int n = sizeof(arr)/sizeof(arr[0]);      int *st = constructst(arr, n);      int qs = 0; //start     int qe = 2; //end     int s = 0;     for(int = 0; < n; ++i) {         for(int j = 0; j < n - s; ++j) {             cout << rmq(st, n, j, j + s) << " ";         }         s += 1;     }     cout << endl;      return 0; } 

of course can use deque. find way smallest element appears @ front of q , size of q never exceeds l. complexity: o(n)