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 |ai − ai+1| if 1≤ i < n, and |an − a1| 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
Problem Author: Semyon Trifochkin
Problem Source: Ural School Programming Contest 2020