Generate the next lexicographic ordering

Given an array of integers, rearrange the elements in-place to form the next sequence in lexicographic order relative to the current arrangement; if no greater ordering exists, return the smallest (sorted ascending) arrangement. The solution should run in O(n) time and O( 1) extra space. Explain the algorithm, prove its correctness, and handle arrays with duplicates. Follow-ups: adapt the approach for arrays that may include negative numbers and for a custom comparator defining the ordering.