After preprocessing find() is O(1):

#! perl -slw
use strict;
use Data::Dump qw[ pp ];

{
    my %V;
    sub preprocess {
        my $aRef = shift;
        push @{ $V{ $aRef->[ $_ ] } }, $_ for 0 .. $#{ $aRef };
        for my $v ( keys %V ) {
            my $last = 0;
            @{ $V{ $v } } = map{ 
                ( $_ ) x ( $_ - $last, $last=$_ )[0] 
            } @{ $V{ $v } };
            push @{ $V{ $v } }, (undef) x( @{ $aRef } - $last );
        }
    }

    sub find{
        my( $i, $v ) = @_;
        return $V{ $v }[ $i ];
    }
}

my @A = qw[ 2 3 43 12 46 7 8 9 90 4 34 4 4 ];
preprocess( \@A );

print "Next value 4 after position $_ is at: ",
    find( $_, 4 ) // 'none'
    for 0 .. $#A;
    
__END__
C:\test>970274
Next value 4 after position 0 is at: 9
Next value 4 after position 1 is at: 9
Next value 4 after position 2 is at: 9
Next value 4 after position 3 is at: 9
Next value 4 after position 4 is at: 9
Next value 4 after position 5 is at: 9
Next value 4 after position 6 is at: 9
Next value 4 after position 7 is at: 9
Next value 4 after position 8 is at: 9
Next value 4 after position 9 is at: 11
Next value 4 after position 10 is at: 11
Next value 4 after position 11 is at: 12
Next value 4 after position 12 is at: none
[download]