We have permutation $p$ of elements $1,\ldots, n$. What is the minimal number of operations required to sort this permutation (in ascending order), where permitted operations are:
a) select some number and insert it in any position
b) select two adjacent numbers and swap them
My intuition is that the answer for the first case is: $n-\operatorname{lis}(p)$ where $\operatorname{lis}(p)$ is the longest increasing subsequence of permutation $p$, because these elements can stay in their positions and every other element we can insert in right position using one operation.
For the second, answer will be the number of inversions in permutation $p$ - that is my observation, I don't see any argument, even such naive like this above;
These are only my intuitions, I'm not sure what are the answers. What is the most interesting for me - how to deduce those answers, or if we can guess them, how to prove we found right formulas?