问题

### Instructions: You are an expert Python programmer. You will be given a question (problem specification) and will generate a correct Python program that matches the specification and passes all tests. You will NOT return anything except for the program.
### Question:
There is an election to choose one winner from N candidates with candidate numbers 1, 2, \ldots, N, and there have been M votes cast.
Each vote is for exactly one candidate, with the i-th vote being for candidate A_i.
The votes will be counted in order from first to last, and after each vote is counted, the current winner will be updated and displayed.
The candidate with the most votes among those counted is the winner. If there are multiple candidates with the most votes, the one with the smallest candidate number is the winner.
For each i = 1, 2, \ldots, M, determine the winner when counting only the first i votes.

Input

The input is given from Standard Input in the following format:
N M
A_1 A_2 \ldots A_M

Output

Print M lines.
The i-th line should contain the winner's candidate number when counting only the first i votes.

Constraints


- 1 \leq N, M \leq 200000
- 1 \leq A_i \leq N
- All input values are integers.

Sample Input 1

3 7
1 2 2 3 1 3 3

Sample Output 1

1
1
2
2
1
1
3

Let C_i denote the number of votes for candidate i.

- After the first vote is counted, (C_1, C_2, C_3) = (1, 0, 0), so the winner is 1.
- After the second vote is counted, (C_1, C_2, C_3) = (1, 1, 0), so the winner is 1.
- After the third vote is counted, (C_1, C_2, C_3) = (1, 2, 0), so the winner is 2.
- After the fourth vote is counted, (C_1, C_2, C_3) = (1, 2, 1), so the winner is 2.
- After the fifth vote is counted, (C_1, C_2, C_3) = (2, 2, 1), so the winner is 1.
- After the sixth vote is counted, (C_1, C_2, C_3) = (2, 2, 2), so the winner is 1.
- After the seventh vote is counted, (C_1, C_2, C_3) = (2, 2, 3), so the winner is 3.

Sample Input 2

100 5
100 90 80 70 60

Sample Output 2

100
90
80
70
60

Sample Input 3

9 8
8 8 2 2 8 8 2 2

Sample Output 3

8
8
8
2
8
8
8
2

### Format: Read the inputs from stdin solve the problem and write the answer to stdout (do not directly test on the sample inputs). Enclose your code within delimiters as follows.
```python
# YOUR CODE HERE
```

### Answer: (use the provided format with backticks)

答案

模型 模型答案 正确答案
金声玉亮2.0 ```python
import sys
input = sys.stdin.read
data = input().split()

N = int(data[0])
M = int(data[1])
votes = list(map(int, data[2:]))

count = [0] * (N + 1)
winner = 0

for i in range(M):
candidate = votes[i]
count[candidate] += 1
if count[candidate] > count[winner] or (count[candidate] == count[winner] and candidate < winner):
winner = candidate
print(winner)
```		 [{"input": "3 7\n1 2 2 3 1 3 3\n", "output": "1\n1\n2\n2\n1\n1\n3\n", "testtype": "stdin"}, {"input": "100 5\n100 90 80 70 60\n", "output": "100\n90\n80\n70\n60\n", "testtype": "stdin"}, {"input": "9 8\n8 8 2 2 8 8 2 2\n", "output": "8\n8\n8\n2\n8\n8\n8\n2\n", "testtype": "stdin"}]
deepseek-r1

```python
def main():
import sys
input = sys.stdin.read().split()
idx = 0
N = int(input[idx])
idx += 1
M = int(input[idx])
idx += 1
A = list(map(int, input[idx:idx + M]))

counts = [0] * (N + 1)
current_max = 0
current_leader = 0

for a in A:
counts[a] += 1
new_count = counts[a]
if new_count > current_max:
current_max = new_count
current_leader = a
elif new_count == current_max:
if a < current_leader:
current_leader = a
print(current_leader)

if __name__ == '__main__':
main()
```		 [{"input": "3 7\n1 2 2 3 1 3 3\n", "output": "1\n1\n2\n2\n1\n1\n3\n", "testtype": "stdin"}, {"input": "100 5\n100 90 80 70 60\n", "output": "100\n90\n80\n70\n60\n", "testtype": "stdin"}, {"input": "9 8\n8 8 2 2 8 8 2 2\n", "output": "8\n8\n8\n2\n8\n8\n8\n2\n", "testtype": "stdin"}]
gpto1 ```python
# YOUR CODE HERE
import sys
import threading
def main():
import sys
import bisect
sys.setrecursionlimit(1 << 25)
N, M = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))
counts = [0] * (N + 1)
max_count = 0
min_candidate_with_max_count = 0
for a in A:
counts[a] +=1
if counts[a] > max_count:
max_count = counts[a]
min_candidate_with_max_count = a
elif counts[a] == max_count:
min_candidate_with_max_count = min(min_candidate_with_max_count, a)
# Output the winner after this vote
print(min_candidate_with_max_count)
threading.Thread(target=main).start()
```		 [{"input": "3 7\n1 2 2 3 1 3 3\n", "output": "1\n1\n2\n2\n1\n1\n3\n", "testtype": "stdin"}, {"input": "100 5\n100 90 80 70 60\n", "output": "100\n90\n80\n70\n60\n", "testtype": "stdin"}, {"input": "9 8\n8 8 2 2 8 8 2 2\n", "output": "8\n8\n8\n2\n8\n8\n8\n2\n", "testtype": "stdin"}]
gpt-4o-2024-08-06 ```python
# YOUR CODE HERE
import sys
input = sys.stdin.read

def main():
data = input().strip().split()
N = int(data[0])
M = int(data[1])
votes = list(map(int, data[2:]))

# Initialize vote counts for each candidate
vote_counts = [0] * (N + 1) # index 0 is unused, candidates are 1-indexed

current_winner = 0
max_votes = 0

for i in range(M):
candidate = votes[i]
vote_counts[candidate] += 1

# Check if this candidate becomes the new winner
if vote_counts[candidate] > max_votes:
max_votes = vote_counts[candidate]
current_winner = candidate
elif vote_counts[candidate] == max_votes:
# If there's a tie, choose the candidate with the smaller number
if candidate < current_winner:
current_winner = candidate

print(current_winner)

if __name__ == "__main__":
main()
```		 [{"input": "3 7\n1 2 2 3 1 3 3\n", "output": "1\n1\n2\n2\n1\n1\n3\n", "testtype": "stdin"}, {"input": "100 5\n100 90 80 70 60\n", "output": "100\n90\n80\n70\n60\n", "testtype": "stdin"}, {"input": "9 8\n8 8 2 2 8 8 2 2\n", "output": "8\n8\n8\n2\n8\n8\n8\n2\n", "testtype": "stdin"}]
Qwen2-72B-Instruct ```python
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=[0]*(n+1)
c=0
d=[]
for i in range(m):
b[a[i]]+=1
if b[a[i]]>=c:
c=b[a[i]]
d.append(a[i])
else:
d.append(d[-1])
for i in d:
print(i)
```
```		 [{"input": "3 7\n1 2 2 3 1 3 3\n", "output": "1\n1\n2\n2\n1\n1\n3\n", "testtype": "stdin"}, {"input": "100 5\n100 90 80 70 60\n", "output": "100\n90\n80\n70\n60\n", "testtype": "stdin"}, {"input": "9 8\n8 8 2 2 8 8 2 2\n", "output": "8\n8\n8\n2\n8\n8\n8\n2\n", "testtype": "stdin"}]
DeepSeek-Coder-V2-Lite-Instruct ```python
# YOUR CODE HERE
import sys
from collections import defaultdict

# Read input
N, M = map(int, sys.stdin.readline().split())
votes = list(map(int, sys.stdin.readline().split()))

# Initialize the count of votes for each candidate
vote_count = defaultdict(int)

# Process each vote
for i in range(M):
vote_count[votes[i]] += 1
max_votes = -1
winner = float('inf')
# Determine the winner with the current votes
for candidate in range(1, N + 1):
if vote_count[candidate] > max_votes or (vote_count[candidate] == max_votes and candidate < winner):
max_votes = vote_count[candidate]
winner = candidate
print(winner)
```

This code reads the number of candidates `N` and the number of votes `M` from the standard input. It then reads the list of votes and processes each vote to update the count of votes for each candidate. After each vote is counted, it determines the current winner based on the maximum number of votes and, in case of a tie, the smallest candidate number, and prints the winner's candidate number.		 [{"input": "3 7\n1 2 2 3 1 3 3\n", "output": "1\n1\n2\n2\n1\n1\n3\n", "testtype": "stdin"}, {"input": "100 5\n100 90 80 70 60\n", "output": "100\n90\n80\n70\n60\n", "testtype": "stdin"}, {"input": "9 8\n8 8 2 2 8 8 2 2\n", "output": "8\n8\n8\n2\n8\n8\n8\n2\n", "testtype": "stdin"}]
Meta-Llama-3.1-405B-Instruct-Turbo ```python
import sys

def solve():
n, m = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))

cnt = [0] * (n + 1)
for i in range(m):
cnt[a[i]] += 1
max_val = max(cnt)
for j in range(1, n + 1):
if cnt[j] == max_val:
print(j)
break

if __name__ == "__main__":
solve()
```		 [{"input": "3 7\n1 2 2 3 1 3 3\n", "output": "1\n1\n2\n2\n1\n1\n3\n", "testtype": "stdin"}, {"input": "100 5\n100 90 80 70 60\n", "output": "100\n90\n80\n70\n60\n", "testtype": "stdin"}, {"input": "9 8\n8 8 2 2 8 8 2 2\n", "output": "8\n8\n8\n2\n8\n8\n8\n2\n", "testtype": "stdin"}]
Meta-Llama-3.1-70B-Instruct-Turbo ```python
import sys

n, m = map(int, input().split())
a = list(map(int, input().split()))

votes = [0] * (n + 1)
winner = 0
for i, x in enumerate(a):
votes[x] += 1
if votes[x] >= votes[winner]:
winner = x
print(winner)
```		 [{"input": "3 7\n1 2 2 3 1 3 3\n", "output": "1\n1\n2\n2\n1\n1\n3\n", "testtype": "stdin"}, {"input": "100 5\n100 90 80 70 60\n", "output": "100\n90\n80\n70\n60\n", "testtype": "stdin"}, {"input": "9 8\n8 8 2 2 8 8 2 2\n", "output": "8\n8\n8\n2\n8\n8\n8\n2\n", "testtype": "stdin"}]
baichuan4 ```python
from collections import defaultdict

# Read the input values
N, M = map(int, input().split())
votes = list(map(int, input().split()))

# Initialize a dictionary to keep track of the vote counts for each candidate
vote_counts = defaultdict(int)

# Initialize the current winner and their vote count
current_winner = None
max_votes = 0

# Process each vote
for i, vote in enumerate(votes):
# Update the vote count for the current vote's candidate
vote_counts[vote] += 1

# Determine if the current vote's candidate is the new winner
if vote_counts[vote] > max_votes or (vote_counts[vote] == max_votes and vote < current_winner):
current_winner = vote
max_votes = vote_counts[vote]

# Print the current winner after processing the i-th vote
print(current_winner)
```
```		 [{"input": "3 7\n1 2 2 3 1 3 3\n", "output": "1\n1\n2\n2\n1\n1\n3\n", "testtype": "stdin"}, {"input": "100 5\n100 90 80 70 60\n", "output": "100\n90\n80\n70\n60\n", "testtype": "stdin"}, {"input": "9 8\n8 8 2 2 8 8 2 2\n", "output": "8\n8\n8\n2\n8\n8\n8\n2\n", "testtype": "stdin"}]
doubao ```python
import collections

N, M = map(int, input().split())
votes = list(map(int, input().split()))

candidates = collections.defaultdict(int)
winner = 1

for i in range(M):
candidates[votes[i]] += 1
max_votes = max(candidates.values())
for candidate, vote_count in candidates.items():
if vote_count == max_votes and candidate < winner:
winner = candidate
print(winner)
```		 [{"input": "3 7\n1 2 2 3 1 3 3\n", "output": "1\n1\n2\n2\n1\n1\n3\n", "testtype": "stdin"}, {"input": "100 5\n100 90 80 70 60\n", "output": "100\n90\n80\n70\n60\n", "testtype": "stdin"}, {"input": "9 8\n8 8 2 2 8 8 2 2\n", "output": "8\n8\n8\n2\n8\n8\n8\n2\n", "testtype": "stdin"}]
gpto1 ```python
# YOUR CODE HERE
import sys
import threading
def main():
import sys
import bisect
sys.setrecursionlimit(1 << 25)
N, M = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))
counts = [0] * (N + 1)
max_count = 0
min_candidate_with_max_count = 0
for a in A:
counts[a] +=1
if counts[a] > max_count:
max_count = counts[a]
min_candidate_with_max_count = a
elif counts[a] == max_count:
min_candidate_with_max_count = min(min_candidate_with_max_count, a)
# Output the winner after this vote
print(min_candidate_with_max_count)
threading.Thread(target=main).start()
```		 [{"input": "3 7\n1 2 2 3 1 3 3\n", "output": "1\n1\n2\n2\n1\n1\n3\n", "testtype": "stdin"}, {"input": "100 5\n100 90 80 70 60\n", "output": "100\n90\n80\n70\n60\n", "testtype": "stdin"}, {"input": "9 8\n8 8 2 2 8 8 2 2\n", "output": "8\n8\n8\n2\n8\n8\n8\n2\n", "testtype": "stdin"}]
kimi ```python
# YOUR CODE HERE
import sys
input = sys.stdin.readline

def main():
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
count = [0] * (N + 1)
winner = 0
max_count = 0
ans = []
for a in A:
count[a] += 1
if count[a] > max_count:
max_count = count[a]
winner = a
elif count[a] == max_count:
if a < winner:
winner = a
ans.append(winner)
print(*ans, sep='\n')
main()
```		 [{"input": "3 7\n1 2 2 3 1 3 3\n", "output": "1\n1\n2\n2\n1\n1\n3\n", "testtype": "stdin"}, {"input": "100 5\n100 90 80 70 60\n", "output": "100\n90\n80\n70\n60\n", "testtype": "stdin"}, {"input": "9 8\n8 8 2 2 8 8 2 2\n", "output": "8\n8\n8\n2\n8\n8\n8\n2\n", "testtype": "stdin"}]
minimax ```python
# YOUR CODE HERE
from collections import Counter

# Read the inputs
N, M = map(int, input().split())
votes = list(map(int, input().split()))

# Initialize a counter to keep track of the votes
vote_count = Counter()

# Initialize a variable to keep track of the current maximum votes
max_votes = 0

# Initialize a variable to keep track of the current winner
winner = 0

# Iterate over each vote
for i, vote in enumerate(votes):
# Update the vote count for the current candidate
vote_count[vote] += 1

# Check if the current candidate has more votes than the current maximum
if vote_count[vote] > max_votes or (vote_count[vote] == max_votes and vote < winner):
# Update the maximum votes and the current winner
max_votes = vote_count[vote]
winner = vote

# Print the current winner
print(winner)
```		 [{"input": "3 7\n1 2 2 3 1 3 3\n", "output": "1\n1\n2\n2\n1\n1\n3\n", "testtype": "stdin"}, {"input": "100 5\n100 90 80 70 60\n", "output": "100\n90\n80\n70\n60\n", "testtype": "stdin"}, {"input": "9 8\n8 8 2 2 8 8 2 2\n", "output": "8\n8\n8\n2\n8\n8\n8\n2\n", "testtype": "stdin"}]
wenxinyiyan ```python
# Read input values
N, M = map(int, input().split())
votes = list(map(int, input().split()))

# Initialize a list to keep track of the number of votes for each candidate
vote_counts = [0] * (N + 1)

# Initialize variables to keep track of the current winner and their vote count
current_winner = None
max_votes = 0

# Iterate over the votes and update the winner after each vote
for i in range(M):
candidate = votes[i]
vote_counts[candidate] += 1 # Increment the vote count for the current candidate

# Check if the current candidate has more votes than the current winner, or if they have the same number of votes but a smaller candidate number
if vote_counts[candidate] > max_votes or (vote_counts[candidate] == max_votes and candidate < current_winner):
current_winner = candidate
max_votes = vote_counts[candidate]

# Print the current winner
print(current_winner)
```		 [{"input": "3 7\n1 2 2 3 1 3 3\n", "output": "1\n1\n2\n2\n1\n1\n3\n", "testtype": "stdin"}, {"input": "100 5\n100 90 80 70 60\n", "output": "100\n90\n80\n70\n60\n", "testtype": "stdin"}, {"input": "9 8\n8 8 2 2 8 8 2 2\n", "output": "8\n8\n8\n2\n8\n8\n8\n2\n", "testtype": "stdin"}]
zhipu ```python
import sys
input = sys.stdin.read

def main():
data = input().split()
n = int(data[0])
m = int(data[1])
votes = list(map(int, data[2:]))

vote_count = [0] * (n + 1)
current_winner = 1
max_votes = 0

results = []

for i in range(m):
candidate = votes[i]
vote_count[candidate] += 1

if vote_count[candidate] > max_votes:
max_votes = vote_count[candidate]
current_winner = candidate
elif vote_count[candidate] == max_votes:
current_winner = min(current_winner, candidate)

results.append(current_winner)

for result in results:
print(result)

if __name__ == "__main__":
main()
```		 [{"input": "3 7\n1 2 2 3 1 3 3\n", "output": "1\n1\n2\n2\n1\n1\n3\n", "testtype": "stdin"}, {"input": "100 5\n100 90 80 70 60\n", "output": "100\n90\n80\n70\n60\n", "testtype": "stdin"}, {"input": "9 8\n8 8 2 2 8 8 2 2\n", "output": "8\n8\n8\n2\n8\n8\n8\n2\n", "testtype": "stdin"}]
deepseek-v3 ```python
# YOUR CODE HERE
import sys
from collections import defaultdict

def main():
N, M = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

vote_counts = defaultdict(int)
max_vote = 0
winner = 0

for a in A:
vote_counts[a] += 1
if vote_counts[a] > max_vote:
max_vote = vote_counts[a]
winner = a
elif vote_counts[a] == max_vote:
if a < winner:
winner = a
print(winner)

if __name__ == "__main__":
main()
```		 [{"input": "3 7\n1 2 2 3 1 3 3\n", "output": "1\n1\n2\n2\n1\n1\n3\n", "testtype": "stdin"}, {"input": "100 5\n100 90 80 70 60\n", "output": "100\n90\n80\n70\n60\n", "testtype": "stdin"}, {"input": "9 8\n8 8 2 2 8 8 2 2\n", "output": "8\n8\n8\n2\n8\n8\n8\n2\n", "testtype": "stdin"}]