D. Shark

Codeforces

IDCF982D

Time1000ms

Memory256MB

Difficulty—

brute forcedata structuresdsutrees

English · Original

Chinese · Translation

Formal · Original

For long time scientists study the behavior of sharks. Sharks, as many other species, alternate short movements in a certain location and long movements between locations. Max is a young biologist. For $n$ days he watched a specific shark, and now he knows the distance the shark traveled in each of the days. All the distances are distinct. Max wants to know now how many locations the shark visited. He assumed there is such an integer $k$ that if the shark in some day traveled the distance strictly less than $k$, then it didn't change the location; otherwise, if in one day the shark traveled the distance greater than or equal to $k$; then it was changing a location in that day. Note that it is possible that the shark changed a location for several consecutive days, in each of them the shark traveled the distance at least $k$. The shark never returned to the same location after it has moved from it. Thus, in the sequence of $n$ days we can find consecutive nonempty segments when the shark traveled the distance less than $k$ in each of the days: each such segment corresponds to one location. Max wants to choose such $k$ that the lengths of all such segments are equal. Find such integer $k$, that the number of locations is as large as possible. If there are several such $k$, print the smallest one. ## Input The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the number of days. The second line contains $n$ distinct positive integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the distance traveled in each of the day. ## Output Print a single integer $k$, such that 1. the shark was in each location the same number of days, 2. the number of locations is maximum possible satisfying the first condition, 3. $k$ is smallest possible satisfying the first and second conditions. [samples] ## Note In the first example the shark travels inside a location on days $1$ and $2$ (first location), then on $4$\-th and $5$\-th days (second location), then on $7$\-th and $8$\-th days (third location). There are three locations in total. In the second example the shark only moves inside a location on the $2$\-nd day, so there is only one location.

长期以来，科学家们研究鲨鱼的行为。鲨鱼和其他许多物种一样，会在某个地点进行短距离移动，并在不同地点之间进行长距离移动。马克斯是一名年轻的生物学家。他观察了一条特定的鲨鱼共 $n$ 天，并记录了鲨鱼每天旅行的距离。所有距离互不相同。马克斯现在想知道鲨鱼访问了多少个地点。他假设存在一个整数 $k$，使得如果鲨鱼在某一天旅行的距离严格小于 $k$，则它没有改变地点；否则，如果某一天鲨鱼旅行的距离大于或等于 $k$，则它在当天改变了地点。注意，鲨鱼可能在连续多天内改变地点，每一天旅行的距离都至少为 $k$。鲨鱼在离开一个地点后绝不会返回。因此，在 $n$ 天的序列中，我们可以找到若干连续的非空段，其中每一天鲨鱼旅行的距离都小于 $k$：每个这样的段对应一个地点。马克斯希望选择一个 $k$，使得所有这些段的长度都相等。请找出一个整数 $k$，使得地点数量尽可能多。如果有多个这样的 $k$，请输出最小的那个。第一行包含一个整数 $n$（$1 lt.eq n lt.eq 10^5$）——天数。第二行包含 $n$ 个互不相同的正整数 $a_1, a_2, dots.h, a_n$（$1 lt.eq a_i lt.eq 10^9$）——每天旅行的距离。在第一个示例中，鲨鱼在第 $1$ 天和第 $2$ 天（第一个地点）内移动，然后在第 $4$ 天和第 $5$ 天（第二个地点），再在第 $7$ 天和第 $8$ 天（第三个地点）移动。总共有三个地点。在第二个示例中，鲨鱼仅在第 $2$ 天在地点内移动，因此只有一个地点。 ## Input 第一行包含一个整数 $n$（$1 lt.eq n lt.eq 10^5$）——天数。第二行包含 $n$ 个互不相同的正整数 $a_1, a_2, dots.h, a_n$（$1 lt.eq a_i lt.eq 10^9$）——每天旅行的距离。 ## Output 输出一个整数 $k$，使得 - 鲨鱼在每个地点停留的天数相同， - 在满足第一个条件的前提下，地点数量尽可能多， - 在满足前两个条件的前提下，$k$ 尽可能小。 [samples] ## Note 在第一个示例中，鲨鱼在第 $1$ 天和第 $2$ 天（第一个地点）内移动，然后在第 $4$ 天和第 $5$ 天（第二个地点），再在第 $7$ 天和第 $8$ 天（第三个地点）移动。总共有三个地点。在第二个示例中，鲨鱼仅在第 $2$ 天在地点内移动，因此只有一个地点。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of days. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of distinct positive integers representing daily distances traveled. Let $ k \in \mathbb{R} $ be a threshold such that: - If $ a_i < k $, the shark remains in the same location on day $ i $. - If $ a_i \geq k $, the shark changes location on day $ i $. A *location segment* is a maximal consecutive subsequence of days where $ a_i < k $. Each such segment corresponds to one distinct location. The shark never returns to a previous location. Let $ L(k) $ denote the number of location segments induced by threshold $ k $. **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ 1 \leq a_i \leq 10^9 $, all $ a_i $ distinct **Objective** Find the smallest integer $ k $ that maximizes $ L(k) $, subject to the constraint that **all location segments have equal length**. That is, among all $ k $ for which the lengths of all maximal consecutive runs of $ a_i < k $ are identical, choose the one maximizing $ L(k) $, and if multiple such $ k $ exist, return the smallest.

Samples

Input #1

8
1 2 7 3 4 8 5 6

Output #1

Input #2

6
25 1 2 3 14 36

Output #2

API Response (JSON)

{
  "problem": {
    "name": "D. Shark",
    "description": {
      "content": "For long time scientists study the behavior of sharks. Sharks, as many other species, alternate short movements in a certain location and long movements between locations. Max is a young biologist. F",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF982D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "For long time scientists study the behavior of sharks. Sharks, as many other species, alternate short movements in a certain location and long movements between locations.\n\nMax is a young biologist. F...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "长期以来，科学家们研究鲨鱼的行为。鲨鱼和其他许多物种一样，会在某个地点进行短距离移动，并在不同地点之间进行长距离移动。\n\n马克斯是一名年轻的生物学家。他观察了一条特定的鲨鱼共 $n$ 天，并记录了鲨鱼每天旅行的距离。所有距离互不相同。马克斯现在想知道鲨鱼访问了多少个地点。他假设存在一个整数 $k$，使得如果鲨鱼在某一天旅行的距离严格小于 $k$，则它没有改变地点；否则，如果某一天鲨鱼旅行的距离大于...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of days.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of distinct positive integers representing daily distances traveled.  \n\nLet $ k \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments