Haha is a humorous god of harmony. Why do I say that?In fact, Haha is forgetful, but Haha thinks that he has an excellent memory. Haha is responsible for balancing the power of various elements in the world. The power is derived from harmony fruits which grow in Hahiland. There are nnn tribes in Hahiland, each takes charge of one element, such as fire, water, etc. There is a fertile field in Hahiland, where the soil is suitable for growing the harmony fruits. Every spring, Haha will divide the field into nnn parts, and each part is of the same total area. Then every tribe will choose one part to be their territory, then sow the harmony seeds on it, and give some element power to the seeds. Although the element power helps the plants to grow well, when the fruits are ripe, they could only be harvested by the one who has the same kind of element power. ``My memory is very good. I don't need to record my divide plan at all!
Haha is a humorous god of harmony. Why do I say that? In fact, Haha is forgetful, but Haha thinks that he has an excellent memory. Haha is responsible for balancing the power of various elements in the world. The power is derived from harmony fruits which grow in Hahiland. There are nnn tribes in Hahiland, each takes charge of one element, such as fire, water, etc. There is a fertile field in Hahiland, where the soil is suitable for growing the harmony fruits. Every spring, Haha will divide the field into nnn parts, and each part is of the same total area. Then every tribe will choose one part to be their territory, then sow the harmony seeds on it, and give some element power to the seeds. Although the element power helps the plants to grow well, when the fruits are ripe, they could only be harvested by the one who has the same kind of element power. ``My memory is very good. I don't need to record my divide plan at all! These are all in my brain clearly!'' Haha said with full confidence. As autumn comes, Haha divides the field into nnn parts again from his memory. But it's actually not the same as last time. People are afraid to tell the harmony god that he is wrong. So they discuss how to allot the nnn parts in order to guarantee the minimum area of plants each tribe could harvest to be as large as possible. The members of Hahiland are wondering how large the minimum area of plants each tribe could harvest could be guaranteed no matter how Haha divides the field, for their future generations. Please calculate it with your wisdom, so that they will be not so anxious. In short, given nnn, determine: minS,A{maxp{mini=1n{∣Si∩Api∣}}}minlimits_{S, A}{maxlimits_{p}{minlimits_{i=1}^{n}{|S_icap A_{p_i}| }}}S,Amin{pmax{i=1minn{∣Si∩Api∣}}} , where S,AS, AS,A denote the field parts(the whole field and the parts can be denoted by some areas in 2D plane) divided in spring and autumn respectively(so ∣S1∣=∣S2∣=⋯=∣Sn∣=∣A1∣=∣A2∣=⋯=∣An∣|S_1| = |S_2| = cdots = |S_n| = |A_1| = |A_2| = cdots = |A_n|∣S1∣=∣S2∣=⋯=∣Sn∣=∣A1∣=∣A2∣=⋯=∣An∣ holds), ppp denotes a permutation of {1,2,⋯ ,n}{1,2,cdots,n}{1,2,⋯,n}(so {p1,p2,⋯ ,pn}={1,2,⋯ ,n}{p_1, p_2, cdots, p_n} = {1, 2, cdots, n}{p1,p2,⋯,pn}={1,2,⋯,n} holds). Moreover, assume the total area of the whole field is 1 and the shape of the whole field doesn't count in this problem as can be seen.
