#1651. 「USACO 2025.1 Bronze」Cow Checkups (Bronze)

内存限制
512 MiB
时间限制
2000 ms
标准输入输出
题目类型
传统
评测方式
文本比较
上传者 admin
题目来源 usaco

显示标签

题目描述

注意:我们建议使用 Python 以外的其他语言以获得本题目的全部分数。

Farmer John 的 )头奶牛站成一行,奶牛 在队伍的最前面,奶牛 在队伍的最后面。FJ 的奶牛也有许多不同的品种。他用从 的整数来表示每一品种。队伍从前到后第 头奶牛的品种是 )。

FJ 正在带他的奶牛们去当地的奶牛医院进行体检。然而,奶牛兽医非常挑剔,仅愿意当队伍中第 头奶牛为品种 )时对其进行体检。

FJ 很懒惰,不想完全重新排列他的奶牛。他将执行以下操作恰好一次。

选择两个整数 ,使得 。反转队伍中第 头奶牛到第 头奶牛之间的奶牛的顺序。 FJ 想要衡量这种方法有多少效果。对于每一个 ,请帮助 FJ 求出使得恰好 头奶牛被检查的不同操作 的数量。两种操作 不同,当且仅当 或者

输入格式

输入的第一行包含

第二行包含

第三行包含

输出格式

输出 行,第 行包含使得 头奶牛被检查的不同操作 的数量。

样例

输入 #1

3
1 3 2
3 2 1

输出 #1

3
3
0
0

输入 #2

3
1 2 3
1 2 3

输出 #2

0
3
0
3

输入 #3

7
1 3 2 2 1 3 2
3 2 2 1 2 3 1

输出 #3

0
6
14
6
2
0
0
0

数据范围与提示

样例解释

样例 #1:

如果 FJ 选择 ,则没有奶牛将会被检查。注意这些操作并没有改变奶牛的位置。 以下操作会导致一头奶牛被检查。

  • :FJ 反转第一头和第二头奶牛的顺序,因此新队伍中每头奶牛的品种将为 。第一头奶牛将会被检查。
  • :FJ 反转第二头和第三头奶牛的顺序,因此新队伍中每头奶牛的品种将为 。第二头奶牛将会被检查。
  • :FJ 反转第一头,第二头和第三头奶牛的顺序,因此新队伍中每头奶牛的品种将为 。第三头奶牛将会被检查。

样例 #2

三种导致 头奶牛被检查的可能操作为

样例 #3

两种导致 头奶牛被检查的可能操作为

子任务

  • 测试点 4-6:
  • 测试点 7-13: 无特殊限制