ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

УрКОП 2020

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. Interesting Conversations

Time limit: 1.0 second
Memory limit: 256 MB
Alice and Bob love receiving guests, and they especially love listening to their conversations. Today Alice is hosting a party because she has defeated Bob in a game, and Bob played optimally. Isn’t it a good enough reason to celebrate?
Alice invited n friends to the party, and they sat down around a circular table. Alice numbered them clockwise from 1 to n. Each friend has interestingness — an integer ai. When all friends got together by the table, they started talking to each other; but each friend only talks to their neighbors to the left and to the right. To determine which conversations are interesting, Alice defined interestingness of i-th conversation as |aiai+1| if 1≤ i < n, and |ana1| if i=n.
Alice wants to eavesdrop on some conversations, but she doesn’t want to upset Bob. So she decided to separate all conversations into two non-empty sets in such a way that the sums of interestingnesses of conversations in both sets are equal. Each conversation should be in exactly one of two sets. Help Alice to find these sets.


The first line contains one integer n (3 ≤ n ≤ 100000).
The second line contains n integers a1, a2, …, an — interestingnesses of friends (1 ≤ ai ≤ 109).


In the first line write “YES” if the conversations can be separated into two sets in such a way, otherwise write “NO”. In the case of “NO” you don’t need to write anything else.
In the second line write m — the size of the first set.
In the third line write space-separated integers p1, p2, …, pm — indices of conversations in the first set.
In the fourth line write k — the size of the second set.
In the fifth line write space-separated integers q1, q2, …, qk — indices of conversations in the second set.


1 2 3
1 2 
Problem Author: Semyon Trifochkin
Problem Source: Ural School Programming Contest 2020
To submit the solution for this problem go to the Problem set: 2156. Interesting Conversations