데크 소트

• 데크 소트 2의 하드 버전. n의 범위가 커진것은 별 문제가 아닌데, 중복 숫자가 들어올수 있다는 것 때문에 전혀 다른 방법으로 풀어야 한다.
• 중복 숫자가 없을 경우에는, 현재 만들어진 덱의 끝에 있는 숫자와 인접한 순위의 숫자가 나오면 무조건 덱에 추가해도 소팅이 가능했다. 하지만 중복 숫자가 있는 경우에는 이야기가 달라지는데, 입력 시퀀스가 5,4,5,6,5 이라고 할 경우, 처음 5를 갖고 새 덱을 만든 다음에 4가 들어왔을 경우, 뒤에 5가 아직 2개 더 나올 예정이지만 4를 앞에다가 붙일 수 있다. 뒤에 나오는 5는 덱의 뒤쪽에 붙이면 되기 때문이다. 하지만 그 뒤에 6이 들어왔을 경우에는 붙일수 없다. 양쪽이 다 막히면 그 뒤에 나오는 5를 넣을수가 없기 때문이다. 결국, 순위가 인접한 숫자라도 상황에 따라서 덱에 붙일수 있는 경우가 있고 새 덱을 만들어야 하는 경우가 생긴다.
• 그렇다면.. 역시 그리디하게, “뒤에 들어올 똑같은 숫자가 있으면 양쪽이 뚫린 경우에만 덱에 추가한다, 한쪽만 뚫려있으면 새 덱을 만든다” 라는 전략을 세워보자. 그 경우에는 이런 반례가 생긴다. 5,4,6,5,3,4 라는 시퀀스가 들어올 경우.. 4는 5의 양쪽이 뚫려있으므로 5앞에 붙이고, 6은 한쪽이 막혀있으므로 세 덱을 만든다. [4,5] / [6] 의 상황인데. 이때 3을 4의 앞에 붙일수가 없으므로 3을 또 새로운 덱으로 만들어야 하고, 최종적으로 [3]/[4,4,5]/[6] 의 세개의 덱이 만들어진다. 하지만 4가 처음 나왔을때 새로운 덱으로 만들었다면 [3,4,4]/[5,5,6] 의 두개의 덱으로 처리할 수 있다. 즉, 시퀀스를 앞에서부터 읽으면서 기존덱에 붙일지 새 덱을 만들지 '그리디하게' 결정하는 것은 불가능하다..
• 다른 방식의 그리디 전략을 세울 수 있다. 시퀀스 안의 숫자를 기존 덱에 붙일지 새 덱을 만들지 하는 결정을, 현재까지 만들어진 덱의 상황을 보고 결정하는 것이 아니라, 아예 맨 처음부터 1번 덱에는 [a,b] 범위의 숫자들을 담고, 2번 덱에는 [c,d]범위의 숫자들들을 담고.. 하겠다는 결정을 내려두고 거기에 맞춰서 처리하는 방법이다.
• 우선.. 중복된 같은 숫자가 여러개에 덱에 나눠져야만 최적이 되는 경우가 있는지를 생각해보면, 그런 경우는 없다는 것을 쉽게 알수 있다. [1,1,2,2]/[2,2,3,4] 와 같은식으로 덱을 만들수 있는 경우는 항상 [1,1,2,2,2,2]/[3,4] 로도 덱을 만들수 있다. 그러므로 각 덱에 포함될 숫자범위가 겹치지 않는 것만을 갖고 생각해도 최적값을 찾을수 있다.
• 이제 각 덱에 들어가야할 숫자 범위를 그리디하게 정하자. 첫번째 덱이 최솟값부터 x까지의 숫자 범위를 갖고 나머지 덱들이 x+1부터 시작하는 숫자들을 커버한다고 할때, x를 가능한 크게 잡는것이 덱의 총 갯수를 줄이는 최적 방법이 된다. 엄밀한 증명을 안해도 직관적으로 쉽게 파악가능하다. 그러면 이제 덱에 넣어질수 있는 x의 최대값이 얼마인지만 찾으면 된다.
• 세 수 a<b<c 가 있고, 그 숫자들의 인덱스가 i[a],i[b],i[c]라고 하면, i[a]<i[b] 이고 i[c]<i[b] 인 경우, 즉 c와 a가 b 보다 먼저 나오는 경우에는 이 세 수를 같은 덱에 넣을 수 없다. 이런 숫자쌍이 하나도 존재하지 않아야만 a,b,c를 모두 같은 덱에 넣을 수 있다. 이것을 잘 정리하면, [a,b-1] 범위를 덱에 넣을 수 있을때, b도 그 덱에 넣을수 있는지를 보기 위해서는 [a,b-1]범위에서 x<y 이고 i[y]>i[x]인 것중 가장 큰 i[y]를 유지하면서 i[b]<i[y]가 있는지를 체크하면 된다. 그런 경우에는 b부터 시작하는 새 덱을 만들어야 하고, 그렇지 않으면 i[y]값을 갱신하면서 b+1에 대해서 테스트하는 식으로 하면 된다.
• 각 숫자에 대해서 가장 왼쪽에 등장하는 숫자의 인덱스와, 가장 우측의 등장하는 인덱스만 계산해서 저장해 놓으면, 각 숫자들에 대해서 새 덱을 만들어야 할지 여부를 O(1) 에 처리 가능하다. 따라서 이부분의 시간 복잡도는 O(m)이고 (m는 unique한 숫자의 갯수), 그 이전에 정렬 과정이 필요하므로 O(mlogm)이 필요하다. 그냥 m대신 n으로 쓰면 O(nlogn)

"""Solution code for "BOJ 1624. 데크 소트".

- Problem link: https://www.acmicpc.net/problem/1624
- Solution link: http://www.teferi.net/ps/problems/boj/1624

Tags: [Greedy]
"""

import collections
import sys

INF = float('inf')


def main():
    N = int(sys.stdin.readline())
    nums = [int(sys.stdin.readline()) for _ in range(N)]

    left_and_right_pos = collections.defaultdict(lambda: (INF, 0))
    for pos, num in enumerate(nums):
        l, r = left_and_right_pos[num]
        left_and_right_pos[num] = (min(l, pos), max(r, pos))

    answer = 0
    left_of_decreasing, right_of_increasing = None, INF
    for _, (l, r) in sorted(left_and_right_pos.items()):
        if right_of_increasing is None:
            if r < left_of_decreasing:
                left_of_decreasing = l
            else:
                right_of_increasing = r
        else:
            if l > right_of_increasing:
                right_of_increasing = r
            else:
                answer += 1
                left_of_decreasing, right_of_increasing = l, None

    print(answer)


if __name__ == '__main__':
    main()