2026 年 USACO竞赛 第二场比赛银奖组问题三—Farmer John Loves Rotations

Farmer John has an array A containing N integers (1≤N≤5⋅105,1≤Ai≤N). He picks his favorite index j and take out a sheet of paper with only  Aj written on it. He can then perform the following operation some number of times:

Cyclically shift all elements in A one spot to the left or one spot to the right. Then, write down Aj on a piece of paper.

Let S denote the set of distinct integers that occur in A. Farmer John wonders what the minimum number of operations he must perform is so that the paper contains all integers that appear in S.

Since it is unclear what FJ's favorite index is, output the answer for all possible favorite indices 1≤j≤N. Note for each index, A is reset to its original form before performing any operations.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N.

The following line contains A1,A2,…,AN.

OUTPUT FORMAT (print output to the terminal / stdout):

Output N space-separated integers, where the i'th integer is the answer for his favorite index j=i.

SAMPLE INPUT:

6
1 2 3 1 3 4

SAMPLE OUTPUT:

4 3 3 4 3 3

The distinct numbers are S={1,2,3,4}. Suppose Farmer John’s favorite index is j=1. He starts off with A1=1 written on a piece of paper. We can track the array A after each cyclic shift Farmer John makes.

Cyclic shift right: FJ writes down A1=4.

4 1 2 3 1 3

Cyclic shift left: FJ writes down A1=1 again.

1 2 3 1 3 4

Cyclic shift left: FJ writes down A1=2.

2 3 1 3 4 1

Cyclic shift left: FJ writes down A1=3.

3 1 3 4 1 2

At this point, Farmer John has written down every number in S using 4 operations.

SAMPLE INPUT:

12
1 1 2 1 1 3 1 1 4 1 1 1

SAMPLE OUTPUT:

8 7 6 7 8 9 8 7 6 7 8 9

SCORING:

Inputs 3-5: N≤500
Inputs 6-8: N≤104
Inputs 9-17: No additional constraints.

Problem credits: Chongtian Ma

历年学员USACO获奖战绩一览

2026赛季5位铂金级
2024-2025赛季5位铂金级
20238位铂金级

USACO 历年战绩

2026赛季战绩

  • 5位铂金级
  • 22位金级
  • 25位银级

2024–2025赛季战绩

翰林考点及辅导学生

  • 5位铂金级
  • 25位金级
  • 38位银级

2023–2024赛季战绩

  • 8位铂金级
  • 32位金级
  • 37位银级

2022–2023赛季战绩

  • 10位铂金级
  • 29位金级
  • 71位银级

篇幅有限,仅展示部分年份战绩。

在线咨询
微信咨询