import java.util.* ;
import java.io.* ;
public class Main
{
public static int firstoccurence( int [ ] nums,int x) {
int n= nums.length ;
int low= 0 ;
int high= n- 1 ;
int res=- 1 ;
while ( low<= high) {
int midd= ( low+ high) / 2 ;
if ( nums[ midd] < x) {
low= midd+ 1 ;
}
else if ( nums[ midd] == x) {
res= midd;
high= midd- 1 ;
}
else {
high= midd- 1 ;
}
}
return res;
}
public static int lastoccurence( int [ ] nums,int x) {
int n= nums.length ;
int low= 0 ;
int high= n- 1 ;
int res=- 1 ;
while ( low<= high) {
int midd= ( low+ high) / 2 ;
if ( nums[ midd] < x) {
low= midd+ 1 ;
}
else if ( nums[ midd] == x) {
res= midd;
low= midd+ 1 ;
}
else {
high= midd- 1 ;
}
}
return res;
}
public static void main
( String [ ] args
) { Scanner sc
= new Scanner
( System .
in ) ; int n= sc.nextInt ( ) ;
int [ ] nums = new int [ n] ; //sorted array given
for ( int i= 0 ; i< n; i++ ) {
nums[ i] = sc.nextInt ( ) ;
}
int k= sc.nextInt ( ) ;
int low= 0 ;
int high = n- 1 ;
while ( low<= high) {
int mid = ( low+ high) / 2 ;
int l1= firstoccurence( nums,nums[ mid] ) ;
int h1= lastoccurence( nums,nums[ mid] ) ;
if ( ( h1- l1+ 1 ) < k) {
System .
out .
print ( "Required element is :" + nums
[ mid
] ) ; break ;
}
else {
if ( ( h1- low+ 1 ) % k == 0 ) { //means no problem till h1 index
low= h1+ 1 ;
}
else if ( ( h1- low+ 1 ) % k != 0 ) { //problem is within low...l1
high= l1- 1 ;
}
}
}
}
}
aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5pby4qOwpwdWJsaWMgY2xhc3MgTWFpbgp7CiAgICBwdWJsaWMgc3RhdGljIGludCBmaXJzdG9jY3VyZW5jZShpbnRbXSBudW1zLGludCB4KXsKICAgICAgICBpbnQgbj1udW1zLmxlbmd0aDsKICAgICAgICAKICAgICAgICBpbnQgbG93PTA7CiAgICAgICAgaW50IGhpZ2g9bi0xOwogICAgICAgIAogICAgICAgIGludCByZXM9LTE7CiAgICAgICAgd2hpbGUobG93PD1oaWdoKXsKICAgICAgICAgICAgaW50IG1pZGQ9KGxvdytoaWdoKS8yOwogICAgICAgICAgICBpZihudW1zW21pZGRdIDwgeCl7CiAgICAgICAgICAgICAgICBsb3c9bWlkZCsxOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UgaWYobnVtc1ttaWRkXSA9PXgpewogICAgICAgICAgICAgICAgcmVzPW1pZGQ7CiAgICAgICAgICAgICAgICBoaWdoPW1pZGQtMTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlewogICAgICAgICAgICAgICAgaGlnaD1taWRkLTE7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgCiAgICAgICAgcmV0dXJuIHJlczsKICAgIH0KICAgIHB1YmxpYyBzdGF0aWMgaW50IGxhc3RvY2N1cmVuY2UoaW50W10gbnVtcyxpbnQgeCl7CiAgICAgICAgaW50IG49bnVtcy5sZW5ndGg7CiAgICAgICAgCiAgICAgICAgaW50IGxvdz0wOwogICAgICAgIGludCBoaWdoPW4tMTsKICAgICAgICAKICAgICAgICBpbnQgcmVzPS0xOwogICAgICAgIHdoaWxlKGxvdzw9aGlnaCl7CiAgICAgICAgICAgIGludCBtaWRkPShsb3craGlnaCkvMjsKICAgICAgICAgICAgaWYobnVtc1ttaWRkXSA8IHgpewogICAgICAgICAgICAgICAgbG93PW1pZGQrMTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlIGlmKG51bXNbbWlkZF0gPT14KXsKICAgICAgICAgICAgICAgIHJlcz1taWRkOwogICAgICAgICAgICAgICAgbG93PW1pZGQrMTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlewogICAgICAgICAgICAgICAgaGlnaD1taWRkLTE7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgCiAgICAgICAgcmV0dXJuIHJlczsKICAgIH0KCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKCQlTY2FubmVyIHNjID0gbmV3IFNjYW5uZXIoU3lzdGVtLmluKTsKCQlpbnQgbj1zYy5uZXh0SW50KCk7CgkJaW50W11udW1zID0gbmV3IGludFtuXTsgLy9zb3J0ZWQgYXJyYXkgZ2l2ZW4KCQkKCQlmb3IoaW50IGk9MDtpPG47aSsrKXsKCQkgICAgbnVtc1tpXT1zYy5uZXh0SW50KCk7CgkJfQoJCWludCBrPXNjLm5leHRJbnQoKTsKCQkKCQlpbnQgbG93PTA7CgkJaW50IGhpZ2ggPW4tMTsKCQkKCQl3aGlsZShsb3c8PWhpZ2gpewoJCSAgICBpbnQgbWlkID0gKGxvdytoaWdoKS8yOwoJCSAgICAKCQkgICAgaW50IGwxPSBmaXJzdG9jY3VyZW5jZShudW1zLG51bXNbbWlkXSk7CgkJICAgIGludCBoMT0gbGFzdG9jY3VyZW5jZShudW1zLG51bXNbbWlkXSk7CgkJICAgIAoJCSAgICBpZigoaDEtbDErMSkgPGspewoJCSAgICAgICAgU3lzdGVtLm91dC5wcmludCgiUmVxdWlyZWQgZWxlbWVudCBpcyA6IiArIG51bXNbbWlkXSk7CgkJICAgICAgICBicmVhazsKCQkgICAgfQoJCSAgICBlbHNlewoJCSAgICAgICAgaWYoKGgxLWxvdysxKSVrID09MCApeyAvL21lYW5zIG5vIHByb2JsZW0gdGlsbCBoMSBpbmRleAoJCSAgICAgICAgICAgIGxvdz1oMSsxOwoJCSAgICAgICAgfQoJCSAgICAgICAgZWxzZSBpZigoaDEtbG93KzEpJWsgIT0wICl7IC8vcHJvYmxlbSBpcyB3aXRoaW4gbG93Li4ubDEKCQkgICAgICAgICAgICAKCQkgICAgICAgICAgICBoaWdoPWwxLTE7CgkJICAgICAgICB9CgkJICAgICAgICAKCQkgICAgfQoJCSAgICAgICAgCgkJICAgIAoJCX0KCX0KfQ==