2026年 北马其顿编程竞赛 (Macedonian programming contests 2026)

赛事等级： 校级选拔赛 (School competition)
内容类型： 竞赛题目 (Competition tasks)

题目名称：门多教授 (Професорот Мендо)

题目描述

经过多年的学习，门多（Mendo）决定成为一名教授。在他的一节课上，他进行了一次测试。门多教授的班级共有 $N$ 名学生，其中第 $i$ 名学生在测试中获得了 $A_i$ 分。

门多正在查看学生成绩单，他想从成绩单中选出一组连续的学生形成一个小组，要求这个小组中没有“最差学生”。

所谓“没有最差学生”，是指在该连续子序列中，最小的得分值必须出现至少两次（即不存在唯一的最小值，从而避免该学生感到受挫）。

请问门多教授共有多少种不同的方式来形成这样的小组？

输入格式

• 第一行包含一个整数 $N$ ($0 < N \le 200,000$)，代表班级学生人数。
• 第二行包含 $N$ 个整数 $A_i$ ($0 \le A_i < 10^9$)，代表每个学生的得分，由空格分隔。

注意： 对于 50% 的测试点，$N \le 1,000$。

输出格式

• 输出一个整数，代表满足条件（连续子序列中最小值出现次数 $\ge 2$）的小组总数。
• 由于结果可能非常大，请输出对 1,000,000,007 取模后的结果。

限制条件

• 时间限制： 1 秒
• 内存限制： 16 MB（极其紧张，需注意空间复杂度）

样例说明

• 输入：

  5
  1 2 2 1 1
  

• 输出：

  6
  

• 解释： 满足条件的 6 组连续子序列为：
  1. (1, 2, 2, 1)：最小值为 1，出现 2 次。
  2. (1, 2, 2, 1, 1)：最小值为 1，出现 3 次。
  3. (2, 2)：最小值为 2，出现 2 次。
  4. (2, 2, 1, 1)：最小值为 1，出现 2 次。
  5. (2, 1, 1)：最小值为 1，出现 2 次。
  6. (1, 1)：最小值为 1，出现 2 次。

版权及来源信息

• 项目： Macedonian Programming Contests (北马其顿编程竞赛)
• 年份： 2026
• 主办/版权方： Združenie na informatičari na Makedonija (ZIM / 北马其顿计算机科学家协会)
• 语言： 马其顿语 (Original in Macedonian)