/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
{
// your code goes here
int nums[]={1,2,3,4,4,5,5,6};
int target=5;
int first=findFirst(nums,target);
int last=findLast(nums,target);
System.
out.
println(first
+" "+last
);
}
public static int findFirst(int []nums,int target){
int l=0;
int r=nums.length-1;
int ans=-1;
while(l<=r){
int mid=(l+r)/2;
if(nums[mid]==target){
ans=mid;
r=mid-1;
}
else if(nums[mid]>target){
r=mid-1;
}
else
{
l=mid+1;
}
}
return ans;
}
public static int findLast(int []nums,int target){
int l=0;
int r=nums.length-1;
int ans=-1;
while(l<=r){
int mid=(l+r)/2;
if(nums[mid]==target){
ans=mid;
l=mid+1;
}
else if(nums[mid]>target){
r=mid-1;
}
else
{
l=mid+1;
}
}
return ans;
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCS8vIHlvdXIgY29kZSBnb2VzIGhlcmUKCQlpbnQgbnVtc1tdPXsxLDIsMyw0LDQsNSw1LDZ9OwoJCWludCB0YXJnZXQ9NTsKCSBpbnQgZmlyc3Q9ZmluZEZpcnN0KG51bXMsdGFyZ2V0KTsKICAgICAgICBpbnQgbGFzdD1maW5kTGFzdChudW1zLHRhcmdldCk7CiAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oZmlyc3QrIiAiK2xhc3QpOwoJCQoJfQoJIHB1YmxpYyBzdGF0aWMgaW50IGZpbmRGaXJzdChpbnQgW11udW1zLGludCB0YXJnZXQpewogICAgICAgIGludCBsPTA7CiAgICAgICAgaW50IHI9bnVtcy5sZW5ndGgtMTsKICAgICAgICBpbnQgYW5zPS0xOwogICAgICAgIHdoaWxlKGw8PXIpewogICAgICAgICBpbnQgbWlkPShsK3IpLzI7CiAgICAgICAgIGlmKG51bXNbbWlkXT09dGFyZ2V0KXsKICAgICAgICAgICAgIGFucz1taWQ7CiAgICAgICAgICAgICByPW1pZC0xOwogICAgICAgICB9CiAgICAgICAgZWxzZSBpZihudW1zW21pZF0+dGFyZ2V0KXsKICAgICAgICAgICAgcj1taWQtMTsKICAgICAgICAgfQogICAgICAgICBlbHNlCiAgICAgICAgIHsKICAgICAgICAgICAgbD1taWQrMTsKCiAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcmV0dXJuIGFuczsKICAgIH0KICAgIHB1YmxpYyBzdGF0aWMgaW50IGZpbmRMYXN0KGludCBbXW51bXMsaW50IHRhcmdldCl7CiAgICAgICAgaW50IGw9MDsKICAgICAgICBpbnQgcj1udW1zLmxlbmd0aC0xOwogICAgICAgIGludCBhbnM9LTE7CiAgICAgICAgd2hpbGUobDw9cil7CiAgICAgICAgIGludCBtaWQ9KGwrcikvMjsKICAgICAgICAgaWYobnVtc1ttaWRdPT10YXJnZXQpewogICAgICAgICAgICAgYW5zPW1pZDsKICAgICAgICAgICAgIGw9bWlkKzE7CiAgICAgICAgIH0KICAgICAgICBlbHNlIGlmKG51bXNbbWlkXT50YXJnZXQpewogICAgICAgICAgICByPW1pZC0xOwogICAgICAgICB9CiAgICAgICAgIGVsc2UKICAgICAgICAgewogICAgICAgICAgICBsPW1pZCsxOwoKICAgICAgICAgfQogICAgICAgIH0KICAgICAgICByZXR1cm4gYW5zOwogICAgfQp9