USE C++ ONLY

You are given a ladder array of n integers. You need to sort it using a Deque. You can use built-in Deque for this problem. The expected Time Complexity is O(n).

A ladder array is an array that is increasing at first, then decreases after that.

For example: [1,3,5,7,2,0] is a ladder array because 1 < 3 < 5 < 7 > 2 > 0. It is increasing till value 7, then it is decreasing after that.

Input	Output
6 1 3 5 7 2 0	0 1 2 3 5 7
5 4 6 2 1 0	0 1 2 4 6

Hint: You just need to compare the values at the front and back of the Deque.