{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003eOnce upon a time there was a famous actress. As you may expect, she played\r\nmostly Antique Comedies most of all. All the people loved her. But she was not\r\ninterested in the crowds. Her big hobby were beads of any kind. Many bead\r\nmakers were working for her and they manufactured new necklaces and\r\nbracelets every day. One day she called her main \u003ci\u003eInspector of Bead\r\nMakers\u003c/i\u003e (\u003ci\u003eIBM\u003c/i\u003e) and told him she wanted a very long and special\r\nnecklace.\r\n\r\n\u003c/p\u003e\u003cp\u003eThe necklace should be made of glass beads of different sizes connected\r\nto each other but without any thread running through the beads, so that\r\nmeans the beads can be disconnected at any point. The actress chose the\r\nsuccession of beads she wants to have and the IBM promised to make the\r\nnecklace. But then he realized a problem. The joint between two neighbouring\r\nbeads is not very robust so it is possible that the necklace will get torn\r\nby its own weight. The situation becomes even worse when the necklace is\r\ndisjoined. Moreover, the point of disconnection is very important. If there\r\nare small beads at the beginning, the possibility of tearing is much higher\r\nthan if there were large beads. IBM wants to test the robustness of a\r\nnecklace so he needs a program that will be able to determine the worst\r\npossible point of disjoining the beads.\r\n\r\n\u003c/p\u003e\u003cp\u003eThe description of the necklace is a string \u003cvar\u003eA \u003d\r\na\u003csub\u003e1\u003c/sub\u003ea\u003csub\u003e2\u003c/sub\u003e ... a\u003csub\u003em\u003c/sub\u003e\u003c/var\u003e\r\nspecifying sizes of the particular beads, where the last character\r\n\u003cvar\u003ea\u003csub\u003em\u003c/sub\u003e\u003c/var\u003e is considered to precede character\r\n\u003cvar\u003ea\u003csub\u003e1\u003c/sub\u003e\u003c/var\u003e in circular fashion. \r\n\r\n\u003c/p\u003e\u003cp\u003eThe disjoint point \u003cvar\u003ei\u003c/var\u003e is said to be worse than the disjoint\r\npoint \u003cvar\u003ej\u003c/var\u003e if and only if the string\r\n\u003cvar\u003ea\u003csub\u003ei\u003c/sub\u003ea\u003csub\u003ei+1\u003c/sub\u003e ... a\u003csub\u003en\u003c/sub\u003ea\u003csub\u003e1\u003c/sub\u003e ...\r\na\u003csub\u003ei-1\u003c/sub\u003e\u003c/var\u003e is lexicografically smaller than the string\r\n\u003cvar\u003ea\u003csub\u003ej\u003c/sub\u003ea\u003csub\u003ej+1\u003c/sub\u003e ... a\u003csub\u003en\u003c/sub\u003ea\u003csub\u003e1\u003c/sub\u003e ...\r\na\u003csub\u003ej-1\u003c/sub\u003e\u003c/var\u003e.\r\nString \u003cvar\u003ea\u003csub\u003e1\u003c/sub\u003ea\u003csub\u003e2\u003c/sub\u003e ... a\u003csub\u003en\u003c/sub\u003e\u003c/var\u003e is\r\nlexicographically smaller than the string\r\n\u003cvar\u003eb\u003csub\u003e1\u003c/sub\u003eb\u003csub\u003e2\u003c/sub\u003e ... b\u003csub\u003en\u003c/sub\u003e\u003c/var\u003e if and only if there\r\nexists an integer \u003cvar\u003ei, i \u0026lt;\u003d n\u003c/var\u003e, so that\r\n\u003cvar\u003ea\u003csub\u003ej\u003c/sub\u003e\u003db\u003csub\u003ej\u003c/sub\u003e\u003c/var\u003e, for each \u003cvar\u003ej, 1 \u0026lt;\u003d j \u0026lt;\r\ni\u003c/var\u003e and \u003cvar\u003ea\u003csub\u003ei\u003c/sub\u003e \u0026lt; b\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e.\r\n\r\n\r\n\u003c/p\u003e\u003ch3\u003eInput\u003c/h3\u003e\r\n\r\n\u003cp\u003eThe input consists of \u003cvar\u003eN\u003c/var\u003e cases. The first line of the input\r\ncontains only positive integer \u003cvar\u003eN\u003c/var\u003e. Then follow the cases. \r\nEach case consists of exactly one line containing necklace description.\r\nMaximal length of each description is 10000 characters. \r\nEach bead is represented by a lower-case character of \r\nthe English alphabet (a--z), where \u003cvar\u003ea \u0026lt; b ... z\u003c/var\u003e.\r\n\r\n\r\n\u003c/p\u003e\u003ch3\u003eOutput\u003c/h3\u003e\r\n\r\n\u003cp\u003eFor each case, print exactly one line containing\r\nonly one integer -- number of the\r\nbead which is the first at the worst possible disjoining, i.e. such\r\n\u003cvar\u003ei\u003c/var\u003e, that the string \u003cvar\u003eA[i]\u003c/var\u003e is lexicographically smallest\r\namong all the \u003cvar\u003en\u003c/var\u003e possible disjoinings of a necklace. If there are\r\nmore than one solution, print the one with the lowest \u003cvar\u003ei\u003c/var\u003e.\r\n\r\n\r\n\u003c/p\u003e\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\nhelloworld\r\namandamanda\r\ndontcallmebfu\r\naaabaaa\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\r\n11\r\n6\r\n5\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\n\u003c/div\u003e"}}]}