Company: DeShaw_5july
Difficulty: medium
Problem Description You are given an integer array arr of length n . A subarray of arr is a contiguous, non-empty block arr[i], arr[i+1], ..., arr[j] with 0 <= i <= j <= n-1 . (inferred - the source does not define "subarray"; contiguous and non-empty is used throughout, and the whole array counts as a subarray of itself.) A subarray is called good if it contains at least one integer that appears exactly once inside that subarray . Occurrences are counted within the subarray only , never across the whole array. You may choose any position of arr and replace the integer stored there with any integer you like. Find the minimum number of positions you must replace so that every subarray of arr becomes good. (inferred - the source states only that a chosen element may be replaced "with any integer"; replacement values are not restricted to the range 1 <= value <= n , and two replaced positions may be given two different values.) Input Format The first line contains a single