I came across an interesting problem and I can't solve it in a good complexity (better than O(qn)):
There are n persons in a row. Initially every person in this row has some value - lets say that i-th person has value a_i. These values are pairwise distinct. Every person gets a mark. There are two conditions:
- If a_i < a_j then j-th person cant get worse mark than i-th person.
- If i < j then j-th person can't get worse mark than i-th person (this condition tells us that sequence of marks is non-decreasing sequence).
There are q operations. In every operation two person are swapped (they swap their values). After each operation you have tell what is maximal number of diffrent marks that these n persons can get.
Do you have any idea?