Longest Prefix With Maximum Frequency
Given an array A of N positive integers, find the length of the longest prefix of A such that the element with the maximum frequency in that prefix appears at least K times. If multiple elements have the same maximum frequency, any one of them can be chosen. If no such prefix exists, output 0.
Input
The first line contains two integers N and K. The second line contains N space-separated integers A_1, A_2, ..., A_N.
Output
Print a single integer: the length of the longest prefix satisfying the condition. If no such prefix exists, print 0.
Constraints
1 <= N <= 200000 1 <= K <= N 1 <= A_i <= 10^9
Example 1
5 3 1 2 1 3 1
5
Prefix [1, 2, 1, 3, 1] has element 1 with frequency 3, which is >= K. Max frequency is 3. Length is 5.
Example 2
7 2 1 1 2 2 3 3 1
7
Prefix [1, 1, 2, 2] has elements 1 and 2 with frequency 2, which is >= K. Max frequency is 2. Length is 4. The longest such prefix is [1, 1, 2, 2, 3, 3, 1], where 1 has frequency 3 >= K=2. Length is 7.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 3 1 2 1 3 1
7 2 1 1 2 2 3 3 1