{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eArup has just created a data structure that makes the two following list transformations in constant O(1) time:\u003c/p\u003e\n\u003cp\u003ea. Take any element in the list and move it to the front.\u0026nbsp;\u003c/p\u003e\n\u003cp\u003eb. Take any element in the list and move it to the back.\u003c/p\u003e\n\u003cp\u003eYou\u0027ve realized that sorting speed can be improved using these transformations. For example, consider the input list:\u0026nbsp;\u003c/p\u003e\n\u003cp\u003e8, 3, 6, 7, 4, 1, 5, 2\u0026nbsp;\u003c/p\u003e\n\u003cp\u003eWe can do the following sequence of transformations to sort this list:\u003c/p\u003e\n\u003cp\u003e8, 3, 7, 4, 1, 5, 2, 6 (move 6 to end)\u0026nbsp;\u003c/p\u003e\n\u003cp\u003e8, 3, 4, 1, 5, 2, 6, 7 (move 7 to end)\u0026nbsp;\u003c/p\u003e\n\u003cp\u003e2, 8, 3, 4, 1, 5, 6, 7 (move 2 to front)\u0026nbsp;\u003c/p\u003e\n\u003cp\u003e1, 2, 8, 3, 4, 5, 6, 7 (move 1 to front)\u0026nbsp;\u003c/p\u003e\n\u003cp\u003e1, 2, 3, 4, 5, 6, 7, 8 (move 8 to end).\u003c/p\u003e\n\u003cp\u003eYou are now curious. Given an input array of distinct values, what is the fewest number of these first/last operations necessary to sort the array?\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eThe Problem:\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003eGiven an initial permutation of the integers 1, 2, ..., n, determine the fewest number of first/last operations necessary to get the list of values sorted in increasing order.\u003cbr\u003e\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eThe Input:\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003eThe first line of input will contain a single positive integer, n (n ≤ 1e5), representing the number of values to be sorted. The next n lines contain one integer each. All of these integers will be distinct values in between 1 and n (inclusive), representing the original order of the data to sort for the input case.\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eThe\u0026nbsp;\u003c/b\u003e\u003cb\u003eOutput:\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003eOn a line by itself, output the fewest number of first/last operations necessary to sort the input list.\u003c/p\u003e"}},{"title":"Sample 1","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\u003e8 \n8 \n3 \n6 \n7 \n4 \n1 \n5 \n2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e"}},{"title":"Sample 2","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 \n1 \n2 \n5 \n3 \n4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e"}}]}