Find the next permutation. Assume that permutation $(n, n - 1, ..., 2, 1)$ is followed by the identity $(1, 2, ..., n - 1, n)$. \InputFile First line contains the number $n~(1 \le n \le 10^5)$ of elements in the permutation. Second line contains a permutation of $n$ integers. \OutputFile Print $n$ numbers --- the next permutation for the given one.