問題一覧 > 通常問題

No.2779 Don't make Pair

レベル : / AI推定難易度 : 550 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 125
作問者 : yuusaan / テスター : 👑 seekworser 👑 amentorimaru
お気に入りにしたユーザー ProblemId : 10973 / 自分の提出
問題文最終更新日: 2024-06-07 22:35:48
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 432 (順位表) の他の問題:

Story

Thanks to your efforts, Yu-san was spared from seeing the unforgivable string, but Yu-san's anger has not subsided yet. The next target is an array.

Yu-san is trying to tear the array into $2$ parts so that identical elements in the array end up separated.

"Couples must be torn apart...!"

However, in reality, this is not always easy to do.

Your job is to figure out, on Yu-san's behalf, how to tear the array so that identical elements do not exist in the same array.

Problem Statement

You are given an array $A$ of length $N$.

Consider choosing an integer $j$ between $1$ and $N-1$, inclusive, and dividing the array into two subsequences $\{ A_1 , A_2 , \dots , A_j \}$ and $\{ A_{j+1} , A_{j+2} , \dots , A_N \}$.

List all $j$ satisfying the following condition in ascending order.

  • Neither of the divided subsequences contains $2$ or more of the same element.

Input

$N$
$A_1$ $A_2$ $\dots$ $A_N$

Constraints

  • $2\leq N \leq 2\times 10^5$
  • $1 \leq A_i \leq 10^9$ $(1\leq i \leq N)$
  • All inputs are integers.

Output

Output $2$ lines.

On the $1$st line, output the number of $j$ satisfying the condition.
On the $2$nd line, output the values of $j$ satisfying the condition in ascending order, separated by spaces.

Print a newline at the end.

Sample

Sample 1
Input
7
3 5 4 3 2 1 9
Output
3
1 2 3

For example, if $j=2$, the array is divided into the $2$ subsequences { $3$ , $5$ } and { $4$ , $3$ , $2$ , $1$ , $9$ }.

Neither of these $2$ arrays contains $2$ or more of the same element, so $j=2$ satisfies the condition.

On the other hand, if $j=5$, the array is divided into the $2$ subsequences { $3$ , $5$ , $4$ , $3$ , $2$ } and { $1$ , $9$ }.

{ $3$ , $5$ , $4$ , $3$ , $2$ } contains $2$ copies of $3$, so $j=5$ does not satisfy the condition.

Sample 2
Input
4
1 1 2 2
Output
0

No value of $j$ satisfies the condition.

Sample 3
Input
5
1 2 3 4 5
Output
4
1 2 3 4

Note that the possible values of $j$ range from $1$ to $N-1$. (The division never produces an empty array.)

Sample 4
Input
3
1 1 1
Output
0

Sample 5
Input
12
4 8 9 10 3 6 4 2 1 7 11 9
Output
4
3 4 5 6

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。