{"ScriptPreparationCode":"function makeid(length) {\r\n var result = \u0027\u0027;\r\n var characters = \u0027ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\u0027;\r\n var charactersLength = characters.length;\r\n for ( var i = 0; i \u003C length; i\u002B\u002B ) {\r\n result \u002B= characters.charAt(Math.floor(Math.random() * charactersLength));\r\n }\r\n return result;\r\n}\r\n\r\n\r\nfunction newElt(isString) {\r\n return isString? makeid(50) : Math.round(Math.random() * Number.MAX_SAFE_INTEGER);\r\n}\r\n\r\nconst numComparator = (a,b) =\u003E a - b;\r\nconst strComparator = (a,b) =\u003E a.localeCompare(b);\r\n\r\nArray.lowerBound = function(array, element, comparator = element.substring? strComparator : numComparator) {\r\n\tlet result = 0;\r\n\tlet count = array.length; // Not n - 1\r\n\tlet match = false;\r\n\twhile (result \u003C count) {\r\n\t\tconst mid = Math.floor((result \u002B count) / 2);\r\n\t\tconst delta = comparator(element, array[mid]);\r\n\t\tif (delta \u003C= 0) {\r\n\t\t\tcount = mid;\r\n\t\t\tif (!delta) {\r\n\t\t\t\tmatch = true;\r\n\t\t\t}\r\n\t\t} else {\r\n\t\t\tresult = mid \u002B 1;\r\n\t\t}\r\n\t}\r\n\tif (match) {\r\n\t\t// search on the right if there is an element equals to elements\r\n\t\tmatch = result;\r\n\t\tdo {\r\n\t\t\tif (element === array[match])\r\n\t\t\t\treturn match;\r\n\t\t} while (\u002B\u002Bmatch\u003Carray.length \u0026\u0026 !comparator(element, array[match]));\r\n\t}\r\n\treturn result;\r\n};\r\n\r\n","TestCases":[{"Name":"Array Num","Code":"let elts = new Array(); \r\nfor(let i = 0; i\u003C10000; \u002B\u002Bi) {\r\n \tconst elt = newElt();\r\n\tlet i = Array.lowerBound(elts, elt);\r\n if(i\u003E=elts.length || elts[i] !== elt) {\r\n\t\telts.splice(i, 0, elt);\r\n }\r\n}","IsDeferred":false},{"Name":"Map Num","Code":"let elts = new Map(); \r\nfor(let i = 0; i\u003C10000; \u002B\u002Bi) {\r\n \tconst elt = newElt();\r\n \tif(!elts.get(elt)) {\r\n elts.set(elt, elt);\r\n \t}\r\n}","IsDeferred":false},{"Name":"Array Str","Code":"let elts = new Array(); \r\nfor(let i = 0; i\u003C10000; \u002B\u002Bi) {\r\n \tconst elt = newElt(true);\r\n\tlet i = Array.lowerBound(elts, elt);\r\n if(i\u003E=elts.length || elts[i] !== elt) {\r\n\t\telts.splice(i, 0, elt);\r\n }\r\n}","IsDeferred":false},{"Name":"Map Str","Code":"let elts = new Map(); \r\nfor(let i = 0; i\u003C10000; \u002B\u002Bi) {\r\n \tconst elt = newElt(true);\r\n \tif(!elts.get(elt)) {\r\n elts.set(elt, elt);\r\n \t}\r\n}","IsDeferred":false}]}