Company: amazon_23april
Difficulty: medium
Amazon Subsequence Prices There are n products being sold on the Amazon Online shopping app. The price of the products will be given by an array of integers where price[i] gives the price of the i-th item. To make the event attractive for any customer to get a gift card, Amazon decided to give special coupons to the buyers. However, the products must be bought in a contiguous subsegment of products and two items of the same price must be in the segment. Find the minimum amount of money it would take to guarantee a gift card. Input Format The first line contains an integer, n, the number of products. The next line contains n integers, price[1..n], where price[i] is the price of the i-th product. Output Format Print the minimum cost of the contiguous subsegment where at least two items have the same price. Constraints 1 ≤ n ≤ 5 * 10 5 0 ≤ price[i] ≤ 10 5 Examples Example 1 Input: 6 2 3 2 1 2 1 Output: 4 The subsegments where not all prices are distinct include [2,3,2] with cost 7, [2,1,2