{"problem":{"name":"multiset","description":{"content":"给定一个 **多重集合**（集合中元素可重复）$S$，请求出一个最大的多重集合 $T$，满足 $T$ 是 $S$ 的一个 **真子集**，且对于 $T$ 中的每一个元素 $i$，要么 $i$ 在 $S$ 中没有前驱，要么 $i$ 在 $S$ 中的前驱 $\\in T$。若有多个大小相同的集合满足条件，则 $T$ 为所有元素之和最大的一个。请输出 $T$ 的大小和其中元素之和。 --- 一个数 $","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9160"},"statements":[{"statement_type":"Markdown","content":"给定一个 **多重集合**（集合中元素可重复）$S$，请求出一个最大的多重集合 $T$，满足 $T$ 是 $S$ 的一个 **真子集**，且对于 $T$ 中的每一个元素 $i$，要么 $i$ 在 $S$ 中没有前驱，要么 $i$ 在 $S$ 中的前驱 $\\in T$。若有多个大小相同的集合满足条件，则 $T$ 为所有元素之和最大的一个。请输出 $T$ 的大小和其中元素之和。\n\n---\n\n一个数 $x$ 在一个集合 $S$ 中的前驱的定义为所有在 $S$ 中且 $<x$ 的元素 $y$ 的最大值。\n\n## Input\n\n第一行一个正整数 $n$，表示 $S$ 的大小。\n\n第二行 $n$ 个正整数，表示 $S$ 中的元素。\n\n## Output\n\n一行两个整数。第一个数表示 $T$ 的大小，第二个数表示 $T$ 的所有元素之和。\n\n[samples]\n\n## Background\n\nZHY 有很多集合。集合多了，也就成了多重集合。\n\n## Note\n\n**样例 $1$ 解释**\n\n$T$ 为 $\\{5,1,4\\}$。\n\n**样例 $2$ 解释**\n\n$T$ 为 $\\{1,4,2,5,7\\}$。\n\n### 数据范围\n\n对于 $30\\%$ 的数据，$n \\le 15$。\n\n对于 $100\\%$ 的数据，$2 \\le n \\le 10^5$，$1 \\le S$ 中的元素 $\\le 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9160","tags":["O2优化"],"sample_group":[["4\n4 5 1 4","3 10"],["6\n1 4 2 8 5 7","5 19"]],"created_at":"2026-03-03 11:09:25"}}