A. Local Extrema

Codeforces

IDCF888A

Time1000ms

Memory256MB

Difficulty—

brute forceimplementation

English · Original

Chinese · Translation

Formal · Original

You are given an array _a_. Some element of this array _a__i_ is a _local minimum_ iff it is strictly less than both of its neighbours (that is, _a__i_ < _a__i_ - 1 and _a__i_ < _a__i_ + 1). Also the element can be called _local maximum_ iff it is strictly greater than its neighbours (that is, _a__i_ > _a__i_ - 1 and _a__i_ > _a__i_ + 1). Since _a_1 and _a__n_ have only one neighbour each, they are neither local minima nor local maxima. An element is called a _local extremum_ iff it is either local maximum or local minimum. Your task is to calculate the number of local extrema in the given array. ## Input The first line contains one integer _n_ (1 ≤ _n_ ≤ 1000) — the number of elements in array _a_. The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 1000) — the elements of array _a_. ## Output Print the number of local extrema in the given array. [samples]

给定一个数组 #cf_span[a]。数组中的某个元素 #cf_span[ai] 被称为 _局部最小值_，当且仅当它严格小于其两个邻居（即 #cf_span[ai < ai - 1] 且 #cf_span[ai < ai + 1]）。类似地，如果元素严格大于其两个邻居（即 #cf_span[ai > ai - 1] 且 #cf_span[ai > ai + 1]），则称为 _局部最大值_。由于 #cf_span[a1] 和 #cf_span[an] 只有一个邻居，因此它们既不是局部最小值也不是局部最大值。如果一个元素是局部最大值或局部最小值，则称其为 _局部极值_。你的任务是计算给定数组中局部极值的个数。第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1000]) —— 数组 #cf_span[a] 中元素的个数。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an] (#cf_span[1 ≤ ai ≤ 1000]) —— 数组 #cf_span[a] 的元素。请输出给定数组中局部极值的个数。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1000]) —— 数组 #cf_span[a] 中元素的个数。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an] (#cf_span[1 ≤ ai ≤ 1000]) —— 数组 #cf_span[a] 的元素。 ## Output 请输出给定数组中局部极值的个数。 [samples]

Let $ a = [a_1, a_2, \dots, a_n] $ be an array of $ n $ integers, where $ 1 \leq n \leq 1000 $ and $ 1 \leq a_i \leq 1000 $. Define a **local extremum** at index $ i $ (for $ 2 \leq i \leq n-1 $) if either: - $ a_i < a_{i-1} $ and $ a_i < a_{i+1} $ (local minimum), or - $ a_i > a_{i-1} $ and $ a_i > a_{i+1} $ (local maximum). The endpoints $ a_1 $ and $ a_n $ are not considered. Let $ E = \{ i \in \{2, 3, \dots, n-1\} \mid (a_i < a_{i-1} \land a_i < a_{i+1}) \lor (a_i > a_{i-1} \land a_i > a_{i+1}) \} $. The number of local extrema is $ |E| $.

Samples

Input #1

3
1 2 3

Output #1

Input #2

4
1 5 2 5

Output #2

API Response (JSON)

{
  "problem": {
    "name": "A. Local Extrema",
    "description": {
      "content": "You are given an array _a_. Some element of this array _a__i_ is a _local minimum_ iff it is strictly less than both of its neighbours (that is, _a__i_ < _a__i_ - 1 and _a__i_ < _a__i_ + 1). Also the ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF888A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an array _a_. Some element of this array _a__i_ is a _local minimum_ iff it is strictly less than both of its neighbours (that is, _a__i_ < _a__i_ - 1 and _a__i_ < _a__i_ + 1). Also the ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个数组 #cf_span[a]。数组中的某个元素 #cf_span[ai] 被称为 _局部最小值_，当且仅当它严格小于其两个邻居（即 #cf_span[ai < ai - 1] 且 #cf_span[ai < ai + 1]）。类似地，如果元素严格大于其两个邻居（即 #cf_span[ai > ai - 1] 且 #cf_span[ai > ai + 1]），则称为 _局部最大值_。由于 #...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ a = [a_1, a_2, \\dots, a_n] $ be an array of $ n $ integers, where $ 1 \\leq n \\leq 1000 $ and $ 1 \\leq a_i \\leq 1000 $.\n\nDefine a **local extremum** at index $ i $ (for $ 2 \\leq i \\leq n-1 $) if ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments