|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||256 MB||2||2||2||100.000%|
The online game you've built in problem "Oha" involves $n$ types of monsters. The monster types are numbered from 1 to $n$, and a monster of $i$-th type has strength $i$ and magical ability $\pi_i$. All magical abilities are different integers between $1$ and $n$, inclusive, in other words, $\pi$ is a permutation. For simplicity, you have generated this permutation uniformly at random.
Now you need to choose the starting teams of monsters for the two sides of the game. Each side must have exactly two monsters in the starting team (they can be of the same type), and the starting teams must be different. However, in order for the game to be balanced, the starting teams must have the same total strength modulo $n$ and the same total magical ability modulo $n$.
More formally, you need to find four integers $a$, $b$, $c$ and $d$ between 1 and $n$ such that:
Note that the above statements are trivially true when $a=c$ and $b=d$, or when $a=d$ and $b=c$. You need to find any other solution, or report that there isn't any. Note that it's allowed for some of the four integers to coincide --- the only restriction is that they can't coincide in the two ways described in the first sentence of this paragraph.
The first line of the input file contains one integer $n$, $2 \le n \le 10^6$. The second line of the input file contains $n$ distinct integers, each between 1 and $n$. The $i$-th of those integers gives the value of $\pi_i$.
It is guaranteed that the permutation was picked uniformly at random out of all permutations of $n$ integers.
If a non-trivial solution exists, print
Ja on the first line of the output file, otherwise print
Nein. In case you printed
Ja, on the second line print four integers between 1 and $n$: $a$, $b$, $c$ and $d$.
5 2 4 3 5 1
Ja 5 5 1 4
There are 50 non-sample testcases in this problem.