{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e Mathematician Ada Lovelace or Lady Lovelace had always been interested in palindromes for his name is one too. A palindrome is a word, number, phrase, or other sequence of symbols that reads the same backwards as forwards. For example, \u003ci\u003eMADAM, PANAMA, ADA\u003c/i\u003e.\n\n\u003cp\u003e Given a string $$$ S $$$, Lady Lovelace wants to figure out the minimal number of characters to be inserted into it to turn it into a palindrome. Help her with that task. \u003c/p\u003e\n\n\u003cp\u003eAs an example, by inserting 2 characters, the string \"A2b2d\" can be transformed into a palindrome (\"dA2b2Ad\" or \"Ad2b2dA\"). However, inserting fewer than 2 characters does not produce a palindrome. \u003cp\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\n\u003cp\u003e The first line contains one integer: the length of the input string N, 3 \u0026lt;\u003d N \u0026lt;\u003d 5000. The second line contains one string with length N. The string is formed from uppercase letters from \u0027A\u0027 to \u0027Z\u0027, lowercase letters from \u0027a\u0027 to \u0027z\u0027 and digits from \u00270\u0027 to \u00279\u0027. Uppercase and lowercase letters are to be considered distinct. \u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\n\u003cp\u003e Output the minimal number of insertions required to obtain a palindrome \u003c/p\u003e "}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e5\nAb2bd\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}