{"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 ascending order by altitude or descending order by altitude.\n\nGiven 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.\n\n## Input\n\nThe 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.\n\n## Output\n\nFor 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.\n\n[samples]\n\n## Note\n\nTwo sets of systems are needed for the sample. One brings down 3, 4 and the other brings down 5, 2, 1.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10490","tags":["搜索","O2优化","深度优先搜索 DFS","剪枝"],"sample_group":[["5 \n3 5 2 4 1 \n0","2"]],"created_at":"2026-03-03 11:09:25"}}