Missile Defence System

Luogu

IDLGP10490

Time2000ms

Memory512MB

DifficultyP3

搜索O2优化深度优先搜索 DFS剪枝

To play against the threats of malicious countries nearby, Country R has updated their missile defence system. The new type system can bring down a series of missiles as long as they are coming in ascending order by altitude or descending order by altitude. Given the heights of a sequence of coming missiles, the general wants to know how many sets of the new type systems are needed to bring down all of them. ## Input The input consists of several test cases. The first line of each test case contains an integer $n (1 \le n \le 50)$. The next line contains n different integers indicating the heights. ## Output For each test case output a single line containing the number of systems needed.For each test case output a single line containing the number of systems needed. [samples] ## Note Two sets of systems are needed for the sample. One brings down 3, 4 and the other brings down 5, 2, 1.

Samples

Input #1

5 
3 5 2 4 1 
0

Output #1

API Response (JSON)

{
  "problem": {
    "name": "Missile Defence System",
    "description": {
      "content": "To play against the threats of malicious countries nearby, Country R has updated their missile defence system. The new type system can bring down a series of missiles as long as they are coming in asc",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10490"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "To play against the threats of malicious countries nearby, Country R has updated their missile defence system. The new type system can bring down a series of missiles as long as they are coming in asc...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments