Cards Flipping

시간 제한1초메모리 제한2048 MB

요약
카드마다 위아래 두 색 중 하나를 골라 위로 보이게 할 때, 위쪽에 나타나는 서로 다른 색의 최대 개수를 구한다.
난이도

보통10점 중 7점

유형
그리디, 그래프, 해시맵
정답자
아직 제출이 없습니다

문제

The magician BB has nn cards in a row on a desk. Each card has two sides with colors. The top side of a card is the side facing upwards. The bottom side of a card is the side facing downwards. Each side of a card has one color. We want to find the maximum number of distinct colors on the top sides. In the following example, we are given 55 cards in a row on a desk. The colors of the top sides of the cards are violet, red, violet, violet, and red from the left to the right as shown in the following figure. The colors of the bottom sides of the cards are red, violet, blue, yellow, and red from the left to the right.

If we flip a card, then the top side and the bottom side of the card are exchanged. If we flip the 33rd and the 44th card from the left, then the colors of the cards on the top sides become like the following.

The number of distinct colors on the top sides becomes 44 which is the maximum for the example.

Given nn cards placed in a row on a desk and the colors on the sides of cards, write a program to output the maximum number of distinct colors on the top sides.

입력

Your program is to read from the standard input. The input starts with a line containing an integer nn (1≤n≤200,0001 ≤ n ≤200\\,000), where nn is the number of cards. The cards are numbered from 11 to nn. In the following two lines, the first line contains the colors on the top sides of cards from the card 11 to the card nn. The second line contains the colors on the bottom sides of cards from the card 11 to the card nn. Each color is represented by a nonnegative integer, not exceeding 10610^6.

출력

Your program is to write to the standard output. Print exactly one line. The line should contain the maximumnumber of distinct colors on the top sides.

예제3

  1. 예제 1

    입력
    5
    0 1 0 0 1
    1 0 2 3 1
    
    예상 출력
    4
    
  2. 예제 2

    입력
    2
    3 5
    5 1
    
    예상 출력
    2
    
  3. 예제 3

    입력
    3
    0 1 0
    1 0 2
    
    예상 출력
    3