{"id":"a382bac3-1763-4178-a06d-9b7593f8a50b","name":"Create Sorted Array Through Instructions","description":"1.Given an integer array instructions.\r\n2.you are asked to create a sorted array from the elements in instructions. You start with another empty array nums. For each element from left to right in instructions, insert it into nums.\r\n3. The cost of each insertion is the minimum of the following:\r\n a)The number of elements currently in nums that are strictly less than instructions[i].\r\n b)The number of elements currently in nums that are strictly greater than instructions[i].\r\n\r\n4.For example, if inserting element 4 into nums = [2,3,4,5], the cost of insertion is min(2, 1) (elements 2 and 3 are less than 4, element 5 is greater than 4) and nums will become [2,3,4,4,5].\r\n5.Return the total cost to insert all elements from instructions into nums.","inputFormat":"The first line of the input contains n,the length of instruction array.The next line contains n integers.","outputFormat":"Return the total cost to insert all elements from instructions into nums.","constraints":"1 <= instructions.length <= 10^5\r\n1 <= instructions[i] <= 10^5","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.BufferedReader;\r\nimport java.io.IOException;\r\nimport java.io.InputStreamReader;\r\n\r\npublic class Main {\r\n\r\n\tpublic static void main(String[] args) throws NumberFormatException, IOException {\r\n\t\t\r\n\t}\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"6\r\n1 2 3 6 5 4","sampleOutput":"3\r\n","questionVideo":"https://www.youtube.com/embed/0KuZRxsHUjM","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"ed294401-c1be-4c10-a3f7-3e2e4f8d9755","name":"Range Queries For Experts","slug":"range-queries-for-experts-903","type":0},{"id":"179d9606-6fc5-4e3a-935e-46a5c0060175","name":"Create Sorted Array Through Instructions","slug":"create-sorted-array-through-instructions","type":1}],"next":{"id":"239cc04b-e6e3-4d31-b45e-7eb280c3807b","name":"Trampoline","type":1,"slug":"trampoline"},"prev":{"id":"cd4ad84c-95ed-49ea-a5b5-25ed0d9bbd4b","name":"2d Binary Indexed Tree","type":1,"slug":"2d-binary-indexed-tree"}}}

Create Sorted Array Through Instructions

1.Given an integer array instructions. 2.you are asked to create a sorted array from the elements in instructions. You start with another empty array nums. For each element from left to right in instructions, insert it into nums. 3. The cost of each insertion is the minimum of the following: a)The number of elements currently in nums that are strictly less than instructions[i]. b)The number of elements currently in nums that are strictly greater than instructions[i]. 4.For example, if inserting element 4 into nums = [2,3,4,5], the cost of insertion is min(2, 1) (elements 2 and 3 are less than 4, element 5 is greater than 4) and nums will become [2,3,4,4,5]. 5.Return the total cost to insert all elements from instructions into nums.

{"id":"a382bac3-1763-4178-a06d-9b7593f8a50b","name":"Create Sorted Array Through Instructions","description":"1.Given an integer array instructions.\r\n2.you are asked to create a sorted array from the elements in instructions. You start with another empty array nums. For each element from left to right in instructions, insert it into nums.\r\n3. The cost of each insertion is the minimum of the following:\r\n a)The number of elements currently in nums that are strictly less than instructions[i].\r\n b)The number of elements currently in nums that are strictly greater than instructions[i].\r\n\r\n4.For example, if inserting element 4 into nums = [2,3,4,5], the cost of insertion is min(2, 1) (elements 2 and 3 are less than 4, element 5 is greater than 4) and nums will become [2,3,4,4,5].\r\n5.Return the total cost to insert all elements from instructions into nums.","inputFormat":"The first line of the input contains n,the length of instruction array.The next line contains n integers.","outputFormat":"Return the total cost to insert all elements from instructions into nums.","constraints":"1 <= instructions.length <= 10^5\r\n1 <= instructions[i] <= 10^5","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.BufferedReader;\r\nimport java.io.IOException;\r\nimport java.io.InputStreamReader;\r\n\r\npublic class Main {\r\n\r\n\tpublic static void main(String[] args) throws NumberFormatException, IOException {\r\n\t\t\r\n\t}\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"6\r\n1 2 3 6 5 4","sampleOutput":"3\r\n","questionVideo":"https://www.youtube.com/embed/0KuZRxsHUjM","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"ed294401-c1be-4c10-a3f7-3e2e4f8d9755","name":"Range Queries For Experts","slug":"range-queries-for-experts-903","type":0},{"id":"179d9606-6fc5-4e3a-935e-46a5c0060175","name":"Create Sorted Array Through Instructions","slug":"create-sorted-array-through-instructions","type":1}],"next":{"id":"239cc04b-e6e3-4d31-b45e-7eb280c3807b","name":"Trampoline","type":1,"slug":"trampoline"},"prev":{"id":"cd4ad84c-95ed-49ea-a5b5-25ed0d9bbd4b","name":"2d Binary Indexed Tree","type":1,"slug":"2d-binary-indexed-tree"}}}
plane

Editor


Loading...

Create Sorted Array Through Instructions

hard

1.Given an integer array instructions. 2.you are asked to create a sorted array from the elements in instructions. You start with another empty array nums. For each element from left to right in instructions, insert it into nums. 3. The cost of each insertion is the minimum of the following: a)The number of elements currently in nums that are strictly less than instructions[i]. b)The number of elements currently in nums that are strictly greater than instructions[i]. 4.For example, if inserting element 4 into nums = [2,3,4,5], the cost of insertion is min(2, 1) (elements 2 and 3 are less than 4, element 5 is greater than 4) and nums will become [2,3,4,4,5]. 5.Return the total cost to insert all elements from instructions into nums.

Constraints

1 <= instructions.length <= 10^5 1 <= instructions[i] <= 10^5

Format

Input

The first line of the input contains n,the length of instruction array.The next line contains n integers.

Output

Return the total cost to insert all elements from instructions into nums.

Example

Sample Input

6 1 2 3 6 5 4

Sample Output

3

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode