Construct a Permutation without an Ordered Arithmetic Triple

### Problem Return any permutation of1 through n such that no positions i<k<j satisfy `2*nums[k] == nums[i]+nums[j]`. At least one valid permutation exists. The restriction concerns the order of positions as well as their numeric values. ```cpp class Solution { public: vector<int> beautifulArray(int n); }; ``` ### Examples **Example 1:** ```text Input: n = 3 Output: [1,3,2] Explanation: The only possible middle index contains3; twice3 differs from1+2. ``` **Example 2:** ```text Input: n = 6 Output: [1,5,3,2,6,4] Explanation: The odd block and even block each come from the valid order[1,3,2] by an affine transformation. Endpoints from different parity blocks cannot average to an integer middle value. ``` ### Constraints - `1 <= n <= 1000`. ### Contract considerations Every integer1 through n must occur exactly once. No particular valid permutation is prescribed. ```hint Read the boundary condition Separate odd and even values so an average cannot cross the parity blocks. ``` ### What a Strong Answer Covers Every integer1 through n must occur exactly once. No particular valid permutation is prescribed. ### Follow-up Questions Optional practice extension, separate from the original task: How could you validate the defining property of a proposed permutation?