// Iterative Code
 
import java.util.*;
import java.io.*;

class GFG 
{ 
	static int lastOcc(int arr[], int n, int x)
	{
		int low = 0, high = n - 1;

		while(low <= high)
		{
			int mid = (low + high) / 2;

			if(x > arr[mid])
				low = mid + 1;

			else if(x < arr[mid])
				high = mid - 1;

			else
			{
				if(mid == n - 1 || arr[mid + 1] != arr[mid])
					return mid;

				else
					low = mid + 1;
			}

		}

		return -1;
	}
	
	public static void main(String args[]) 
	{
	    int arr[] = {5, 10, 10, 10, 10, 20, 20}, n = 7;
	    
	    int x = 10;
	    
	    System.out.println(lastOcc(arr, n, x));   // OUTPUT : 4
    } 
    
}
 
 
 
 
 
 
// Recursive Code
 
import java.util.*;
import java.io.*;

class GFG 
{ 
	static int lastOcc(int arr[], int low, int high, int x, int n)
	{
		if(low > high)
			return -1;

		int mid = (low + high) / 2;

		if(x > arr[mid])
			return lastOcc(arr, mid + 1, high, x, n);

		else if(x < arr[mid])
			return lastOcc(arr, low, mid - 1, x, n);

		else
		{
			if(mid == n - 1 || arr[mid + 1] != arr[mid])
				return mid;

			else
				return lastOcc(arr, mid + 1, high, x, n);
		}
	}
	
	public static void main(String args[]) 
	{
	    int arr[] = {5, 10, 10, 10, 10, 20, 20}, n = 7;
	    
	    int x = 10;
	    
	    System.out.println(lastOcc(arr, 0, n - 1, x, n));   // OUTPUT : 4
    } 

}