## Intuition The problem requires us to construct the lexicographically smallest sequence possible by adding elements of a permutation to a deque. The key insight is to always maintain the smallest possible element at the front of the deque. This ensures that the sequence remains as small as possible lexicographically. ## Approach 1. **Initialization**: Start with an empty deque. 2. **Iterate through the permutation**: - For each element in the permutation, decide whether to add it to the front or the back of the deque. - If the current element is smaller than or equal to the front element of the deque, add it to the front. Otherwise, add it to the back. 3. **Output the deque**: After processing all elements, the deque will contain the lexicographically smallest sequence. This approach ensures that the smallest possible element is always at the front, which helps in maintaining the lexicographical order. ## Complexity - **Time Complexity**: \(O(n)\) per test case, where \(n\) is the size of the permutation. This is because each element is processed exactly once. - **Space Complexity**: \(O(n)\) for storing the deque. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n; cin >> n; deque dq; for (int i = 0; i < n; ++i) { int x; cin >> x; if (dq.empty() || x < dq.front()) { dq.push_front(x); } else { dq.push_back(x); } } for (int i = 0; i < n; ++i) { cout << dq[i] << " "; } cout << "\n"; } return 0; } ``` This solution reads the number of test cases and for each test case, processes the permutation to construct the smallest lexicographical sequence using a deque. The decision to add each element to the front or back of the deque is based on comparing it with the current front element of the deque. This ensures the sequence remains as small as possible lexicographically.

Permutation Minimization by Deque

Problem Details