When a beauty number becomes replaced by another number in a range, after a few updates it will be several blocks continuously with the same numbers. You have to merge them in one big block. Use segment tree to do this. You can also use square root decomposition in this problem.
Expected run-time complexity: O(n × log n).