But I still a little confused with the "use lib" and the BEGIN block, which one is executed first, the "use lib" or the BEGIN block?

BEGIN blocks are executed as soon as they are fully compiled, i.e. when the } is reached.
use statements are executed as soon as they are fully compiled, i.e. when the ; is reached.
In other words, whichever ends first gets executed first.

Where the BEGIN block exactly should be? The very beginning of the script, even before "use strict; use warnning"?

Before useing any modules that require the changed @INC. If it finds utf8, strict, warnings with the default @INC, I'd load those first. That's just my personal preference.